[analyzer] Added a reusable constraint system to the CloneDetector

[teemperor]

Summary

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 is hard coded into the
CloneDetector which makes it hard to understand and extend.

To fix this, this patch implements a system of reusable constraints that are used to filter clones. The system is build upon the Constraint class and its subclasses which each filter one type of clones. To actually filter a set of clones, a list of constraints needs to be created and passed to the CloneDetector which apply them one after another on a list of CloneGroups.

This patch also migrates all previously hard coded constraints to the new system.

[teemperor]

• Add description
• Make sure functions in CloneDetection.cpp are in a more logical order.

[teemperor]

• Rebased patch.
• Renamed passes to constraints.

[v.g.vassilev]

include/clang/Analysis/CloneDetection.h

235 ↗

(On Diff #68680)

I am still unsure about the name. It is too generic. What about CloneConstraint?

[NoQ]

include/clang/Analysis/CloneDetection.h

243 ↗

(On Diff #68680)

I might be wishing a lot, but i've a feeling this interface should be more obvious, i.e. understandable without reading the cpp code.

For example, what is the difference between acceptsHashGroup and acceptsGroup? I don't think the difference is about accepting different kinds of groups ("hash"-groups vs. "non-hash" groups). If two items X and Y are similar in some sense (and here we have methods with similar names and similar prototypes, and the reader would instantly notice that), it's a good trick to first confirm that these are similar, and then highlight the difference: "However, unlike X, the Y is...".

Another example - are these accept... functions supposed to be "pure" (just have a look at the sequence or a group and say if we accept it), or are they supposed to change state of the constraint object? I wish it was obvious from just looking at the interface.

If i wished for even more, i wish this interface could consist of only one method. It seems that this interface is complicated because of performance considerations. So i'd probably want to know more about these considerations, how exactly do all the methods fit together and what is the efficient way of using them.

In order to solve this problem, probably the comment before the class could be extended to explain the big picture. I'd also do my best to understand things better, and probably come up with a wording that would look better from a bystander point of view. Here are a few examples of what seems easier to understand:

• "/// First, CloneDetector filters out groups that are obviously out of place... Then, it takes one prototype from each group and repeatedly asks the Constraint object if other clones of the group are similar to the prototype..."
• "/// If it is obvious just by looking at this group that all sequences in it shouldn't ever be reported, override this callback to notify CloneDetector about that and save some performance..."
• "/// In this callback you may record the property of the prototype you're interested in, so that later you could quickly compare other sequences to it..."

[NoQ]

Here's some pseudo-code of the way i see it.

// This interface mimics CloneDetector's interface, hence omnipotent but useless.

class BasicConstraint {
public:
  virtual void add(const StmtSequence &S) = 0;
  virtual vector<CloneGroup> findClones() = 0;
};

// This constraint separates statements by their hash values.
// Useful for the first pass, when we can't afford the number of sequences
// to slow us down.

class HashingConstraint: public BasicConstraint {
  map<hash_t, CloneGroup> M;

public:
  virtual hash_t hash(const StmtSequence &S) = 0;

  virtual void add(const StmtSequence &S) override {
    M[hash(S)].append(S);
  }
  virtual vector<CloneGroup> findClones() override {
    vector<CloneGroup> V;
    for (I in M)
      V.append(I.second);
    return V;
  }
};

// This interface does pairwise comparisons via the provided compare() function.
// Quadratic but easy to use for later passes.

class ComparingConstraint {
  vector<CloneGroup> V;

public:
  virtual void compare(const StmtSequence &LHS, const StmtSequence &RHS) = 0;

  virtual void add(const StmtSequence &S) override {
    for (auto G in V) {
      if (compare(G[0], S))
        G.append(S);
      else
        V[V.length()].append(S);
    }
  }
  vector<CloneGroup> findClones() override {
    return V;
  }
};

And inherit custom constraints from these building blocks, probably provide more building blocks. Feel free to add const/static stuff and replace virtuals with recursive templates :)

[mehdi_amini]

(Quick stylistic comments)

include/clang/Analysis/CloneDetection.h

224 ↗

(On Diff #68680)

Use of \brief is deprecated (we enabled auto brief quite some time ago).

417 ↗

(On Diff #68680)

= default

419 ↗

(On Diff #68680)

No need for virtual on override.

[teemperor]

• Rebased patch to the current trunk state.
• Replaced runtime polymorphism with templates.
• Constraint interface now only has one method signature.

[teemperor]

• I ran all real-world tests (sqlite, etc.) before rebasing to trunk. I'm not 100% confident that I correctly merged everything, so I'll rerun them just in case. The normal clang test-suite passes, so it looks good.

[teemperor]

• Removed all the deprecated \briefs

I couldn't find any actual regression in the code now, so from my side it's ok to merge it.

[NoQ]

I'm sorry for the delays; i'm humbly requesting a couple more weeks to get back to this awesome stuff.

[v.g.vassilev]

We were planning adding some extra unittests, too...

[NoQ]

I think this is awesome.

Would anybody like to move concrete constraint class definitions to a separate header + translation unit, so that to highlight how simple the primary interface is to a person who haven't gone through all the discussion?

include/clang/Analysis/CloneDetection.h

172 ↗

(On Diff #89084)

Strange spacing.

178 ↗

(On Diff #89084)

Should this pair of functions be made static?

218–219 ↗

(On Diff #89084)

While you could enforce this with static_assert<is_base_of<CloneConstraint, T>> in the detector, i think we shouldn't be strictly enforcing this.

Providing useful utility functions is pretty much the only purpose of this class, so it intends to be useful, but this shouldn't block users from implementing the constrain() method completely from scratch.

Also, we could probably move the method that groups clones by hashes here as the third utility method, if more than one hash function is eventually used(?)

318 ↗

(On Diff #89084)

This comment looks incomplete.

lib/Analysis/CloneDetection.cpp

308 ↗

(On Diff #89084)

I remember some buildbots complained about conflicting names between variables and classes. Could we rename the Stmt parameter? Something like Seq is fine with me.

335–336 ↗

(On Diff #89084)

In particular, this method doesn't use any CloneConstraint's utility methods, as far as i understand.

lib/StaticAnalyzer/Checkers/CloneChecker.cpp

81–83 ↗

(On Diff #89084)

Yay. I like how it looks.

[v.g.vassilev]

lib/StaticAnalyzer/Checkers/CloneChecker.cpp

147 ↗

(On Diff #89084)

Could you transform the TODO into a FIXME?

172 ↗

(On Diff #89084)

Could you add a FIXME here?

[xiangzhai]

Hi Raphael,

Thanks for your awesome job!

I have read about the slide of "LLVM: built-in scalable code clone detection based on semantic analysis", and sent email to Shamil for asking "Is Code clone detection in LLVM compiler infrastructure available?" he replied me that the implementation (in LLVM IR layer?) is unavailable - close source. so I pay more attention to your implementation without LLVM IR, but I am really really really care about:

1. Performance. I use scan-build -k -v -enable-checker alpha.clone.CloneChecker to static analysis K3B, it almost spend one hour! optimization plan?
2. False Positive. I use Coverity scan K3B to compare with CloneDetector, there is NO false positive when detecting Copy-paste issue by setting pattern to ignore Qt Meta-Object Compiler and other auto-generated source files. perhaps CloneChecker is able to learn this way to low false positive?

Thanks again for your great job!

Regards,
Leslie Zhai

[teemperor]

Thanks for the review Artem!

Changes:

• No longer including the old LLVM hashing header.
• Fixed the messed up comment formatting when i removed all the \briefs...
• CloneConstraint is now just a collection of static methods and its no longer necessary to inherit from it. (Maybe we can just replace it in the future with a namespace in the future? I don't like free floating functions and they don't fit into the CloneDetector interface, so this felt like the least-ugly way to do it.)
• Renamed Stmt to Seq to prevent that one warning Artem mentioned.
• Added a example unittest that shows a bit how to use the API and how to create your own Constraint.
• StmtSequence now uses Decl* instead of ASTContext. We get the ASTContext over the stored Decl, but with a Decl we can do better heuristics for StmtSequence::contains and we can do fast filtering based on function name etc.

[teemperor]

Hey Leslie,

regarding performance: Last time I checked we spend most of the time on the verification of the hash values. We can do some tricks to make this faster (like delaying the verification to the end of the constraints where we have much less clones and therefore less overhead with this)

regarding false-positives: We will do some basic stuff to reduce them soon-ish (e.g. increasing the minimum clone size default value, filtering those generated files). Afterwards we probably need some fancier way of teaching the checker what is a valid clone and what not.

If you have some actual bugs that are found by the checker, please send them to me (teemperor [AT] gmail.com) that we can add them to the regression tests :)

include/clang/Analysis/CloneDetection.h

218–219 ↗

(On Diff #89084)

Everything done here beside the hashing, because I think we need to do a few changes there in the future that need some more discussion. For example:

• Split up hashing and verifying them into different constraints. This could drastically improve performance because verification of hashes id currently the biggest time-consumer on an average code-base (at least that was the case the last time I profiled :) ). Depending on how we do this we might need to rely to a certain degree on the unique-ness property of the hash codes...

• Unify the hashing we do with the hashing that we use in the AST. I think we should wait here until we are sure that this is the right thing to do and that the code is mature enough.

lib/StaticAnalyzer/Checkers/CloneChecker.cpp

81–83 ↗

(On Diff #89084)

\o/

[xiangzhai]

Hi Raphael,

Thanks for your reply!

regarding performance: Last time I checked we spend most of the time on the verification of the hash values. We can do some tricks to make this faster (like delaying the verification to the end of the constraints where we have much less clones and therefore less overhead with this)

regarding false-positives: We will do some basic stuff to reduce them soon-ish (e.g. increasing the minimum clone size default value, filtering those generated files). Afterwards we probably need some fancier way of teaching the checker what is a valid clone and what not.

If you have some actual bugs that are found by the checker, please send them to me (teemperor [AT] gmail.com) that we can add them to the regression tests :)

I will test your updated patch tomorrow by testing with KDE/GNOME real projects.

Regards,
Leslie Zhai

[teemperor]

Well this patch won't change a lot with the false-positives or performance (it's more refactoring) :)

[teemperor]

• Remove the assert(ChildHash) which is obviously wrong code that just rarely fails.

[teemperor]

• auto to const auto to be more consistent with LLVM style.

[v.g.vassilev]

I am very happy to see this converging! Thanks for the work and perseverance! LGTM.

[xiangzhai]

Hi Raphael,

Congratulate the patch was accepted!

Well this patch won't change a lot with the false-positives or performance (it's more refactoring) :)

So may I Teach CloneDetection about Qt Meta-Object Compiler and filter other auto-generated source files base on your patch? thanks a lot!

Regards,
Leslie Zhai

[teemperor]

• Remove the mysterious unicode-character at the start of CloneDetection.cpp
• Fixed formatting of the comment in CloneDetectionTest.cpp
• Fixed comment in StmtSequence::contains that was still talking about checking for translation units even though we compared declarations.

I think this is everything from my side for now :)

[xiangzhai]

Hi Raphael,

Then I will rebase my patch D31320 please review it when you have free time, thanks a lot!

Regards,
Leslie Zhai

[NoQ]

Yay, i think this is good to go. Sorry again for being slow>< I guess i'd go ahead and land this patch soon.

include/clang/Analysis/CloneDetection.h

228 ↗

(On Diff #93503)

All right, now this is essentially a namespace :)

[teemperor]

Change it to a namespace when merging if you prefer that :). Thanks for the review!

[NoQ]

Hmm, reverted because i'm seeing crashes on some buildbots (works for me though).

It's crashing somewhere in saveHash, seems that some Stmts are null. For instance, http://lab.llvm.org:8011/builders/clang-cmake-aarch64-42vma/builds/5998 :

#0 0x00000000015356f8 llvm::sys::PrintStackTrace(llvm::raw_ostream&) (/home/buildslave/buildslave/clang-cmake-aarch64-42vma/stage1/./bin/clang+0x15356f8)
#1 0x0000000001533a58 llvm::sys::RunSignalHandlers() (/home/buildslave/buildslave/clang-cmake-aarch64-42vma/stage1/./bin/clang+0x1533a58)
#2 0x0000000001533d0c SignalHandler(int) (/home/buildslave/buildslave/clang-cmake-aarch64-42vma/stage1/./bin/clang+0x1533d0c)
#3 0x000003ffb5150510 (linux-vdso.so.1+0x510)
#4 0x0000000002b562f0 clang::Stmt::children() (/home/buildslave/buildslave/clang-cmake-aarch64-42vma/stage1/./bin/clang+0x2b562f0)
#5 0x00000000029772a4 clang::RecursiveCloneTypeIIConstraint::saveHash(clang::Stmt const*, clang::Decl const*, std::vector<std::pair<unsigned long, clang::StmtSequence>, std::allocator<std::pair<unsigned long, clang::StmtSequence> > >&) (/home/buildslave/buildslave/clang-cmake-aarch64-42vma/stage1/./bin/clang+0x29772a4)
#6 0x00000000029795a8 clang::RecursiveCloneTypeIIConstraint::constrain(std::vector<llvm::SmallVector<clang::StmtSequence, 8u>, std::allocator<llvm::SmallVector<clang::StmtSequence, 8u> > >&) (/home/buildslave/buildslave/clang-cmake-aarch64-42vma/stage1/./bin/clang+0x29795a8)
#7 0x00000000026786b0 void clang::CloneDetector::findClones<clang::RecursiveCloneTypeIIConstraint, clang::MinComplexityConstraint, clang::MinGroupSizeConstraint, clang::OnlyLargestCloneConstraint>(std::vector<llvm::SmallVector<clang::StmtSequence, 8u>, std::allocator<llvm::SmallVector<clang::StmtSequence, 8u> > >&, clang::RecursiveCloneTypeIIConstraint, clang::MinComplexityConstraint, clang::MinGroupSizeConstraint, clang::OnlyLargestCloneConstraint) (/home/buildslave/buildslave/clang-cmake-aarch64-42vma/stage1/./bin/clang+0x26786b0)
#8 0x0000000002678b08 void clang::ento::check::EndOfTranslationUnit::_checkEndOfTranslationUnit<(anonymous namespace)::CloneChecker>(void*, clang::TranslationUnitDecl const*, clang::ento::AnalysisManager&, clang::ento::BugReporter&) (/home/buildslave/buildslave/clang-cmake-aarch64-42vma/stage1/./bin/clang+0x2678b08)
#9 0x00000000028a9394 clang::ento::CheckerManager::runCheckersOnEndOfTranslationUnit(clang::TranslationUnitDecl const*, clang::ento::AnalysisManager&, clang::ento::BugReporter&) (/home/buildslave/buildslave/clang-cmake-aarch64-42vma/stage1/./bin/clang+0x28a9394)
#10 0x000000000204b62c (anonymous namespace)::AnalysisConsumer::HandleTranslationUnit(clang::ASTContext&) [clone .part.4452] [clone .constprop.4496] (/home/buildslave/buildslave/clang-cmake-aarch64-42vma/stage1/./bin/clang+0x204b62c)
#11 0x000000000206de78 clang::ParseAST(clang::Sema&, bool, bool) (/home/buildslave/buildslave/clang-cmake-aarch64-42vma/stage1/./bin/clang+0x206de78)
#12 0x00000000019e96b4 clang::FrontendAction::Execute() (/home/buildslave/buildslave/clang-cmake-aarch64-42vma/stage1/./bin/clang+0x19e96b4)
#13 0x00000000019c2c70 clang::CompilerInstance::ExecuteAction(clang::FrontendAction&) (/home/buildslave/buildslave/clang-cmake-aarch64-42vma/stage1/./bin/clang+0x19c2c70)
#14 0x0000000001a64f30 clang::ExecuteCompilerInvocation(clang::CompilerInstance*) (/home/buildslave/buildslave/clang-cmake-aarch64-42vma/stage1/./bin/clang+0x1a64f30)
#15 0x0000000000998420 cc1_main(llvm::ArrayRef<char const*>, char const*, void*) (/home/buildslave/buildslave/clang-cmake-aarch64-42vma/stage1/./bin/clang+0x998420)
#16 0x0000000000963b94 main (/home/buildslave/buildslave/clang-cmake-aarch64-42vma/stage1/./bin/clang+0x963b94)
#17 0x000003ffb4bef68c __libc_start_main (/lib64/libc.so.6+0x1f68c)
#18 0x00000000009950e8 _start (/home/buildslave/buildslave/clang-cmake-aarch64-42vma/stage1/./bin/clang+0x9950e8)

[spatel]

In D23418#719139, @NoQ wrote:

Hmm, reverted because i'm seeing crashes on some buildbots (works for me though).

It's crashing somewhere in saveHash, seems that some Stmts are null. For instance, http://lab.llvm.org:8011/builders/clang-cmake-aarch64-42vma/builds/5998 :

Not sure if it helps, but there was this build warning:
/home/buildslave/buildslave/clang-cmake-aarch64-39vma/llvm/tools/clang/lib/Analysis/CloneDetection.cpp:395:36: warning: ‘S’ is used uninitialized in this function [-Wuninitialized]

[teemperor]

• Renamed variable from 'S' to 'Child' to make the buildbots happy (and because it's more expressive)
• Fixed the name of the unit test.

[teemperor]

lib/Analysis/CloneDetection.cpp

395 ↗

(On Diff #94337)

I couldn't reproduce, but from what I assume form the warning and the crash that we confused the compiler here by naming both the loop-variable and the parameter 'S'. I renamed it to 'Child' which /should/ fix it.

[NoQ]

$ cat test.c
#include <stdio.h>
int main() {
  int i = 5;
  {
    int i = i;
    printf("%d\n", i);
  }
  return 0;
}
$ clang test.c
$ ./a.out
32767
$ clang test.c -Xclang -ast-dump
...
`-FunctionDecl 0x7ff82d8eac78 <test.c:2:1, line:9:1> line:2:5 main 'int ()'
  `-CompoundStmt 0x7ff82d8eb070 <col:12, line:9:1>
    |-DeclStmt 0x7ff82d8eadb0 <line:3:3, col:12>
    | `-VarDecl 0x7ff82d8ead30 <col:3, col:11> col:7 i 'int' cinit
    |   `-IntegerLiteral 0x7ff82d8ead90 <col:11> 'int' 5
    |-CompoundStmt 0x7ff82d8eb010 <line:4:3, line:7:3>
    | |-DeclStmt 0x7ff82d8eae78 <line:5:5, col:14>
    | | `-VarDecl 0x7ff82d8eadd8 <col:5, col:13> col:9 used i 'int' cinit
    | |   `-ImplicitCastExpr 0x7ff82d8eae60 <col:13> 'int' <LValueToRValue>
    | |     `-DeclRefExpr 0x7ff82d8eae38 <col:13> 'int' lvalue Var 0x7ff82d8eadd
...

It seems that in int i = i; the i in the new i, which is already declared by now, just not initialized yet, rather than the old i.

[teemperor]

I think for range loops work differently:

#include <cassert>
#include <vector>
#include <iostream>

struct Foo {
int* begin() const { assert(false); }
int* end() const { assert(false); }
void bar() const { std::cout << "Different behavior" << std::endl; }
};

int main() {

std::vector<Foo*> F;
F.resize(1);
for (const Foo* F : F) {
    F->bar();
}

}

teemperor@ftlserver ~/test> clang++ test.cpp -std=c++11 ; and ./a.out
Different behavior

cfe/trunk/include/clang/Analysis/CloneDetection.h

 /// This file defines classes for searching and anlyzing source code clones.
 ///
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_AST_CLONEDETECTION_H
 #define LLVM_CLANG_AST_CLONEDETECTION_H
 
 #include "clang/Basic/SourceLocation.h"
-#include "llvm/ADT/Hashing.h"
-#include "llvm/ADT/StringMap.h"
-
+#include "llvm/ADT/SmallVector.h"
 #include <vector>
 
 namespace clang {
 
 class Stmt;
 class Decl;
 class VarDecl;
 class ASTContext;
 class CompoundStmt;
 
-/// \brief Identifies a list of statements.
+/// Identifies a list of statements.
 ///
 /// Can either identify a single arbitrary Stmt object, a continuous sequence of
 /// child statements inside a CompoundStmt or no statements at all.
 class StmtSequence {
   /// If this object identifies a sequence of statements inside a CompoundStmt,
   /// S points to this CompoundStmt. If this object only identifies a single
   /// Stmt, then S is a pointer to this Stmt.
   const Stmt *S;
 
-  /// The related ASTContext for S.
-  ASTContext *Context;
+  /// The declaration that contains the statements.
+  const Decl *D;
 
   /// If EndIndex is non-zero, then S is a CompoundStmt and this StmtSequence
   /// instance is representing the CompoundStmt children inside the array
   /// [StartIndex, EndIndex).
   unsigned StartIndex;
   unsigned EndIndex;
 
 public:
-  /// \brief Constructs a StmtSequence holding multiple statements.
+  /// Constructs a StmtSequence holding multiple statements.
   ///
   /// The resulting StmtSequence identifies a continuous sequence of statements
   /// in the body of the given CompoundStmt. Which statements of the body should
   /// be identified needs to be specified by providing a start and end index
   /// that describe a non-empty sub-array in the body of the given CompoundStmt.
   ///
   /// \param Stmt A CompoundStmt that contains all statements in its body.
-  /// \param Context The ASTContext for the given CompoundStmt.
+  /// \param Decl The Decl containing this Stmt.
   /// \param StartIndex The inclusive start index in the children array of
   ///                   \p Stmt
   /// \param EndIndex The exclusive end index in the children array of \p Stmt.
-  StmtSequence(const CompoundStmt *Stmt, ASTContext &Context,
-               unsigned StartIndex, unsigned EndIndex);
+  StmtSequence(const CompoundStmt *Stmt, const Decl *D, unsigned StartIndex,
+               unsigned EndIndex);
 
-  /// \brief Constructs a StmtSequence holding a single statement.
+  /// Constructs a StmtSequence holding a single statement.
   ///
   /// \param Stmt An arbitrary Stmt.
-  /// \param Context The ASTContext for the given Stmt.
-  StmtSequence(const Stmt *Stmt, ASTContext &Context);
+  /// \param Decl The Decl containing this Stmt.
+  StmtSequence(const Stmt *Stmt, const Decl *D);
 
-  /// \brief Constructs an empty StmtSequence.
+  /// Constructs an empty StmtSequence.
   StmtSequence();
 
   typedef const Stmt *const *iterator;
 
   /// Returns an iterator pointing to the first statement in this sequence.
   iterator begin() const;
 
   /// Returns an iterator pointing behind the last statement in this sequence.
if (S == nullptr)
       return 0;
     return 1;
   }
 
   /// Returns true if and only if this StmtSequence contains no statements.
   bool empty() const { return size() == 0; }
 
   /// Returns the related ASTContext for the stored Stmts.
-  ASTContext &getASTContext() const {
-    assert(Context);
-    return *Context;
+  ASTContext &getASTContext() const;
+
+  /// Returns the declaration that contains the stored Stmts.
+  const Decl *getContainingDecl() const {
+    assert(D);
+    return D;
   }
 
   /// Returns true if this objects holds a list of statements.
   bool holdsSequence() const { return EndIndex != 0; }
 
   /// Returns the start sourcelocation of the first statement in this sequence.
   ///
   /// This method should only be called on a non-empty StmtSequence object.
public:
   /// Returns true if and only if this sequence covers a source range that
   /// contains the source range of the given sequence \p Other.
   ///
   /// This method should only be called on a non-empty StmtSequence object
   /// and passed a non-empty StmtSequence object.
   bool contains(const StmtSequence &Other) const;
 };
 
-/// \brief Searches for clones in source code.
+/// Searches for similar subtrees in the AST.
+///
+/// First, this class needs several declarations with statement bodies which
+/// can be passed via analyzeCodeBody. Afterwards all statements can be
+/// searched for clones by calling findClones with a given list of constraints
+/// that should specify the wanted properties of the clones.
 ///
-/// First, this class needs a translation unit which is passed via
-/// \p analyzeTranslationUnit . It will then generate and store search data
-/// for all statements inside the given translation unit.
-/// Afterwards the generated data can be used to find code clones by calling
-/// \p findClones .
+/// The result of findClones can be further constrained with the constrainClones
+/// method.
 ///
 /// This class only searches for clones in exectuable source code
 /// (e.g. function bodies). Other clones (e.g. cloned comments or declarations)
 /// are not supported.
 class CloneDetector {
+
 public:
-  typedef unsigned DataPiece;
+  /// A collection of StmtSequences that share an arbitrary property.
+  typedef llvm::SmallVector<StmtSequence, 8> CloneGroup;
 
-  /// Holds the data about a StmtSequence that is needed during the search for
-  /// code clones.
-  struct CloneSignature {
-    /// \brief The hash code of the StmtSequence.
-    ///
-    /// The initial clone groups that are formed during the search for clones
-    /// consist only of Sequences that share the same hash code. This makes this
-    /// value the central part of this heuristic that is needed to find clones
-    /// in a performant way. For this to work, the type of this variable
-    /// always needs to be small and fast to compare.
-    ///
-    /// Also, StmtSequences that are clones of each others have to share
-    /// the same hash code. StmtSequences that are not clones of each other
-    /// shouldn't share the same hash code, but if they do, it will only
-    /// degrade the performance of the hash search but doesn't influence
-    /// the correctness of the result.
-    size_t Hash;
+  /// Generates and stores search data for all statements in the body of
+  /// the given Decl.
+  void analyzeCodeBody(const Decl *D);
 
-    /// \brief The complexity of the StmtSequence.
-    ///
-    /// This value gives an approximation on how many direct or indirect child
-    /// statements are contained in the related StmtSequence. In general, the
-    /// greater this value, the greater the amount of statements. However, this
-    /// is only an approximation and the actual amount of statements can be
-    /// higher or lower than this value. Statements that are generated by the
-    /// compiler (e.g. macro expansions) for example barely influence the
-    /// complexity value.
-    ///
-    /// The main purpose of this value is to filter clones that are too small
-    /// and therefore probably not interesting enough for the user.
-    unsigned Complexity;
+  /// Constrains the given list of clone groups with the given constraint.
+  /// The constraint is expected to have a method with the signature
+  ///     `void constrain(std::vector<CloneDetector::CloneGroup> &Sequences)`
+  /// as this is the interface that the CloneDetector uses for applying the
+  /// constraint. The constraint is supposed to directly modify the passed list
+  /// so that all clones in the list fulfill the specific property this
+  /// constraint ensures.
+  template <typename T>
+  static void constrainClones(std::vector<CloneGroup> &CloneGroups, T C) {
+    C.constrain(CloneGroups);
+  }
+
+  /// Constrains the given list of clone groups with the given list of
+  /// constraints.
+  /// The constraints are applied in sequence in the order in which they are
+  /// passed to this function.
+  template <typename T1, typename... Ts>
+  static void constrainClones(std::vector<CloneGroup> &CloneGroups, T1 C,
+                              Ts... ConstraintList) {
+    constrainClones(CloneGroups, C);
+    constrainClones(CloneGroups, ConstraintList...);
+  }
+
+  /// Searches for clones in all previously passed statements.
+  /// \param Result Output parameter to which all created clone groups are
+  ///               added.
+  /// \param Passes The constraints that should be applied to the result.
+  template <typename... Ts>
+  void findClones(std::vector<CloneGroup> &Result, Ts... ConstraintList) {
+    // The initial assumption is that there is only one clone group and every
+    // statement is a clone of the others. This clone group will then be
+    // split up with the help of the constraints.
+    CloneGroup AllClones;
+    AllClones.reserve(Sequences.size());
+    for (const auto &C : Sequences) {
+      AllClones.push_back(C);
+    }
+
+    Result.push_back(AllClones);
+
+    constrainClones(Result, ConstraintList...);
+  }
+
+private:
+  CloneGroup Sequences;
+};
+
+/// This class is a utility class that contains utility functions for building
+/// custom constraints.
+class CloneConstraint {
+public:
+  /// Removes all groups by using a filter function.
+  /// \param CloneGroups The list of CloneGroups that is supposed to be
+  ///                    filtered.
+  /// \param Filter The filter function that should return true for all groups
+  ///               that should be removed from the list.
+  static void
+  filterGroups(std::vector<CloneDetector::CloneGroup> &CloneGroups,
+               std::function<bool(const CloneDetector::CloneGroup &)> Filter) {
+    CloneGroups.erase(
+        std::remove_if(CloneGroups.begin(), CloneGroups.end(), Filter),
+        CloneGroups.end());
+  }
+
+  /// Splits the given CloneGroups until the given Compare function returns true
+  /// for all clones in a single group.
+  /// \param CloneGroups A list of CloneGroups that should be modified.
+  /// \param Compare The comparison function that all clones are supposed to
+  ///                pass. Should return true if and only if two clones belong
+  ///                to the same CloneGroup.
+  static void splitCloneGroups(
+      std::vector<CloneDetector::CloneGroup> &CloneGroups,
+      std::function<bool(const StmtSequence &, const StmtSequence &)> Compare);
+};
 
-    /// \brief Creates an empty CloneSignature without any data.
-    CloneSignature() : Complexity(1) {}
+/// Searches all children of the given clones for type II clones (i.e. they are
+/// identical in every aspect beside the used variable names).
+class RecursiveCloneTypeIIConstraint {
+
+  /// Generates and saves a hash code for the given Stmt.
+  /// \param S The given Stmt.
+  /// \param D The Decl containing S.
+  /// \param StmtsByHash Output parameter that will contain the hash codes for
+  ///                    each StmtSequence in the given Stmt.
+  /// \return The hash code of the given Stmt.
+  ///
+  /// If the given Stmt is a CompoundStmt, this method will also generate
+  /// hashes for all possible StmtSequences in the children of this Stmt.
+  size_t saveHash(const Stmt *S, const Decl *D,
+                  std::vector<std::pair<size_t, StmtSequence>> &StmtsByHash);
 
-    CloneSignature(llvm::hash_code Hash, unsigned Complexity)
-        : Hash(Hash), Complexity(Complexity) {}
-  };
+public:
+  void constrain(std::vector<CloneDetector::CloneGroup> &Sequences);
 
-  /// Holds group of StmtSequences that are clones of each other and the
-  /// complexity value (see CloneSignature::Complexity) that all stored
-  /// StmtSequences have in common.
-  struct CloneGroup {
-    std::vector<StmtSequence> Sequences;
-    CloneSignature Signature;
+/// Ensures that every clone has at least the given complexity.
+///
+/// Complexity is here defined as the total amount of children of a statement.
+/// This constraint assumes the first statement in the group is representative
+/// for all other statements in the group in terms of complexity.
+class MinComplexityConstraint {
+  unsigned MinComplexity;
+
+public:
+  MinComplexityConstraint(unsigned MinComplexity)
+      : MinComplexity(MinComplexity) {}
 
-    CloneGroup() {}
+  size_t calculateStmtComplexity(const StmtSequence &Seq,
+                                 const std::string &ParentMacroStack = "");
 
-    CloneGroup(const StmtSequence &Seq, CloneSignature Signature)
-        : Signature(Signature) {
-      Sequences.push_back(Seq);
-    }
+  void constrain(std::vector<CloneDetector::CloneGroup> &CloneGroups) {
+    CloneConstraint::filterGroups(
+        CloneGroups, [this](const CloneDetector::CloneGroup &A) {
+          if (!A.empty())
+            return calculateStmtComplexity(A.front()) < MinComplexity;
+          else
+            return false;
+        });
+};
 
-    /// \brief Returns false if and only if this group should be skipped when
-    ///        searching for clones.
-    bool isValid() const {
-      // A clone group with only one member makes no sense, so we skip them.
-      return Sequences.size() > 1;
-    }
-  };
+/// Ensures that all clone groups contain at least the given amount of clones.
+class MinGroupSizeConstraint {
+  unsigned MinGroupSize;
+
+public:
+  MinGroupSizeConstraint(unsigned MinGroupSize = 2)
+      : MinGroupSize(MinGroupSize) {}
+
+  void constrain(std::vector<CloneDetector::CloneGroup> &CloneGroups) {
+    CloneConstraint::filterGroups(CloneGroups,
+                                  [this](const CloneDetector::CloneGroup &A) {
+                                    return A.size() < MinGroupSize;
+                                  });
 
-  /// \brief Generates and stores search data for all statements in the body of
-  ///        the given Decl.
-  void analyzeCodeBody(const Decl *D);
+/// Ensures that no clone group fully contains another clone group.
+struct OnlyLargestCloneConstraint {
+  void constrain(std::vector<CloneDetector::CloneGroup> &Result);
+};
 
-  /// \brief Stores the CloneSignature to allow future querying.
-  void add(const StmtSequence &S, const CloneSignature &Signature);
+/// Analyzes the pattern of the referenced variables in a statement.
+class VariablePattern {
 
-  /// \brief Searches the provided statements for clones.
-  ///
-  /// \param Result Output parameter that is filled with a list of found
-  ///               clone groups. Each group contains multiple StmtSequences
-  ///               that were identified to be clones of each other.
-  /// \param MinGroupComplexity Only return clones which have at least this
-  ///                           complexity value.
-  /// \param CheckPatterns Returns only clone groups in which the referenced
-  ///                      variables follow the same pattern.
-  void findClones(std::vector<CloneGroup> &Result, unsigned MinGroupComplexity,
-                  bool CheckPatterns = true);
+  /// 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;
+    /// The statement in the code where the variable was referenced.
+    const Stmt *Mention;
+
+    VariableOccurence(size_t KindID, const Stmt *Mention)
+        : KindID(KindID), Mention(Mention) {}
+  };
+
+  /// 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;
+
+  /// Adds a new variable referenced to this pattern.
+  /// \param VarDecl The declaration of the variable that is referenced.
+  /// \param Mention The SourceRange where this variable is referenced.
+  void addVariableOccurence(const VarDecl *VarDecl, const Stmt *Mention);
+
+  /// Adds each referenced variable from the given statement.
+  void addVariables(const Stmt *S);
 
-  /// \brief Describes two clones that reference their variables in a different
-  ///        pattern which could indicate a programming error.
+public:
+  /// Creates an VariablePattern object with information about the given
+  /// StmtSequence.
+  VariablePattern(const StmtSequence &Sequence) {
+    for (const Stmt *S : Sequence)
+      addVariables(S);
+  }
+
+  /// Describes two clones that reference their variables in a different pattern
+  /// which could indicate a programming error.
   struct SuspiciousClonePair {
-    /// \brief Utility class holding the relevant information about a single
-    ///        clone in this pair.
+    /// Utility class holding the relevant information about a single
+    /// clone in this pair.
     struct SuspiciousCloneInfo {
       /// The variable which referencing in this clone was against the pattern.
       const VarDecl *Variable;
       /// Where the variable was referenced.
       const Stmt *Mention;
       /// The variable that should have been referenced to follow the pattern.
       /// If Suggestion is a nullptr then it's not possible to fix the pattern
       /// by referencing a different variable in this clone.
       const VarDecl *Suggestion;
       SuspiciousCloneInfo(const VarDecl *Variable, const Stmt *Mention,
                           const VarDecl *Suggestion)
           : Variable(Variable), Mention(Mention), Suggestion(Suggestion) {}
       SuspiciousCloneInfo() {}
     };
     /// The first clone in the pair which always has a suggested variable.
     SuspiciousCloneInfo FirstCloneInfo;
     /// This other clone in the pair which can have a suggested variable.
     SuspiciousCloneInfo SecondCloneInfo;
   };
 
-  /// \brief Searches the provided statements for pairs of clones that don't
-  ///        follow the same pattern when referencing variables.
-  /// \param Result Output parameter that will contain the clone pairs.
-  /// \param MinGroupComplexity Only clone pairs in which the clones have at
-  ///                           least this complexity value.
-  void findSuspiciousClones(std::vector<SuspiciousClonePair> &Result,
-                            unsigned MinGroupComplexity);
+  /// Counts the differences between this pattern and the given one.
+  /// \param Other The given VariablePattern to compare with.
+  /// \param FirstMismatch Output parameter that will be filled with information
+  ///        about the first difference between the two patterns. This parameter
+  ///        can be a nullptr, in which case it will be ignored.
+  /// \return Returns the number of differences between the pattern this object
+  ///         is following and the given VariablePattern.
+  ///
+  /// For example, the following statements all have the same pattern and this
+  /// function would return zero:
+  ///
+  ///   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) and would have two differences when
+  /// compared with one of the statements above.
+  ///
+  ///   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.
+  unsigned countPatternDifferences(
+      const VariablePattern &Other,
+      VariablePattern::SuspiciousClonePair *FirstMismatch = nullptr);
+};
 
-private:
-  /// Stores all encountered StmtSequences alongside their CloneSignature.
-  std::vector<std::pair<CloneSignature, StmtSequence>> Sequences;
+/// Ensures that all clones reference variables in the same pattern.
+struct MatchingVariablePatternConstraint {
+  void constrain(std::vector<CloneDetector::CloneGroup> &CloneGroups);
 };
 
 } // end namespace clang
 
 #endif // LLVM_CLANG_AST_CLONEDETECTION_H

cfe/trunk/lib/Analysis/CloneDetection.cpp

 #include "clang/AST/StmtVisitor.h"
 #include "clang/Lex/Lexer.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/MD5.h"
 #include "llvm/Support/raw_ostream.h"
 
 using namespace clang;
 
-StmtSequence::StmtSequence(const CompoundStmt *Stmt, ASTContext &Context,
+StmtSequence::StmtSequence(const CompoundStmt *Stmt, const Decl *D,
                            unsigned StartIndex, unsigned EndIndex)
-    : S(Stmt), Context(&Context), StartIndex(StartIndex), EndIndex(EndIndex) {
+    : S(Stmt), D(D), StartIndex(StartIndex), EndIndex(EndIndex) {
   assert(Stmt && "Stmt must not be a nullptr");
   assert(StartIndex < EndIndex && "Given array should not be empty");
   assert(EndIndex <= Stmt->size() && "Given array too big for this Stmt");
 }
 
-StmtSequence::StmtSequence(const Stmt *Stmt, ASTContext &Context)
-    : S(Stmt), Context(&Context), StartIndex(0), EndIndex(0) {}
+StmtSequence::StmtSequence(const Stmt *Stmt, const Decl *D)
+    : S(Stmt), D(D), StartIndex(0), EndIndex(0) {}
 
 StmtSequence::StmtSequence()
-    : S(nullptr), Context(nullptr), StartIndex(0), EndIndex(0) {}
+    : S(nullptr), D(nullptr), StartIndex(0), EndIndex(0) {}
 
 bool StmtSequence::contains(const StmtSequence &Other) const {
-  // If both sequences reside in different translation units, they can never
-  // contain each other.
-  if (Context != Other.Context)
+  // If both sequences reside in different declarations, they can never contain
+  // each other.
+  if (D != Other.D)
     return false;
 
-  const SourceManager &SM = Context->getSourceManager();
+  const SourceManager &SM = getASTContext().getSourceManager();
 
   // Otherwise check if the start and end locations of the current sequence
   // surround the other sequence.
   bool StartIsInBounds =
       SM.isBeforeInTranslationUnit(getStartLoc(), Other.getStartLoc()) ||
       getStartLoc() == Other.getStartLoc();
   if (!StartIsInBounds)
     return false;

 StmtSequence::iterator StmtSequence::end() const {
   if (!holdsSequence()) {
     return reinterpret_cast<StmtSequence::iterator>(&S) + 1;
   }
   auto CS = cast<CompoundStmt>(S);
   return CS->body_begin() + EndIndex;
 }
 
+ASTContext &StmtSequence::getASTContext() const {
+  assert(D);
+  return D->getASTContext();
+}
+
 SourceLocation StmtSequence::getStartLoc() const {
   return front()->getLocStart();
 }
 
 SourceLocation StmtSequence::getEndLoc() const { return back()->getLocEnd(); }
 
 SourceRange StmtSequence::getSourceRange() const {
   return SourceRange(getStartLoc(), getEndLoc());
 }
 
-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;
-    /// The statement in the code where the variable was referenced.
-    const Stmt *Mention;
-
-    VariableOccurence(size_t KindID, const Stmt *Mention)
-        : KindID(KindID), Mention(Mention) {}
-  };
-
-  /// 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.
-  /// \param Mention The SourceRange where this variable is referenced.
-  void addVariableOccurence(const VarDecl *VarDecl, const Stmt *Mention) {
-    // 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, Mention);
-        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(), Mention);
-    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, D);
-    }
-
-    // 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 Counts the differences between this pattern and the given one.
-  /// \param Other The given VariablePattern to compare with.
-  /// \param FirstMismatch Output parameter that will be filled with information
-  ///        about the first difference between the two patterns. This parameter
-  ///        can be a nullptr, in which case it will be ignored.
-  /// \return Returns the number of differences between the pattern this object
-  ///         is following and the given VariablePattern.
-  ///
-  /// For example, the following statements all have the same pattern and this
-  /// function would return zero:
-  ///
-  ///   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) and would have two differences when
-  /// compared with one of the statements above.
-  ///
-  ///   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.
-  unsigned countPatternDifferences(
-      const VariablePattern &Other,
-      CloneDetector::SuspiciousClonePair *FirstMismatch = nullptr) {
-    unsigned NumberOfDifferences = 0;
-
-    assert(Other.Occurences.size() == Occurences.size());
-    for (unsigned i = 0; i < Occurences.size(); ++i) {
-      auto ThisOccurence = Occurences[i];
-      auto OtherOccurence = Other.Occurences[i];
-      if (ThisOccurence.KindID == OtherOccurence.KindID)
-        continue;
-
-      ++NumberOfDifferences;
-
-      // If FirstMismatch is not a nullptr, we need to store information about
-      // the first difference between the two patterns.
-      if (FirstMismatch == nullptr)
-        continue;
-
-      // Only proceed if we just found the first difference as we only store
-      // information about the first difference.
-      if (NumberOfDifferences != 1)
-        continue;
-
-      const VarDecl *FirstSuggestion = nullptr;
-      // If there is a variable available in the list of referenced variables
-      // which wouldn't break the pattern if it is used in place of the
-      // current variable, we provide this variable as the suggested fix.
-      if (OtherOccurence.KindID < Variables.size())
-        FirstSuggestion = Variables[OtherOccurence.KindID];
-
-      // Store information about the first clone.
-      FirstMismatch->FirstCloneInfo =
-          CloneDetector::SuspiciousClonePair::SuspiciousCloneInfo(
-              Variables[ThisOccurence.KindID], ThisOccurence.Mention,
-              FirstSuggestion);
-
-      // Same as above but with the other clone. We do this for both clones as
-      // we don't know which clone is the one containing the unintended
-      // pattern error.
-      const VarDecl *SecondSuggestion = nullptr;
-      if (ThisOccurence.KindID < Other.Variables.size())
-        SecondSuggestion = Other.Variables[ThisOccurence.KindID];
-
-      // Store information about the second clone.
-      FirstMismatch->SecondCloneInfo =
-          CloneDetector::SuspiciousClonePair::SuspiciousCloneInfo(
-              Other.Variables[OtherOccurence.KindID], OtherOccurence.Mention,
-              SecondSuggestion);
-
-      // SuspiciousClonePair guarantees that the first clone always has a
-      // suggested variable associated with it. As we know that one of the two
-      // clones in the pair always has suggestion, we swap the two clones
-      // in case the first clone has no suggested variable which means that
-      // the second clone has a suggested variable and should be first.
-      if (!FirstMismatch->FirstCloneInfo.Suggestion)
-        std::swap(FirstMismatch->FirstCloneInfo,
-                  FirstMismatch->SecondCloneInfo);
-
-      // This ensures that we always have at least one suggestion in a pair.
-      assert(FirstMismatch->FirstCloneInfo.Suggestion);
-    }
-
-    return NumberOfDifferences;
-  }
-};
-}
-
-/// \brief Prints the macro name that contains the given SourceLocation into
-///        the given raw_string_ostream.
+/// Prints the macro name that contains the given SourceLocation into the given
+/// raw_string_ostream.
 static void printMacroName(llvm::raw_string_ostream &MacroStack,
                            ASTContext &Context, SourceLocation Loc) {
   MacroStack << Lexer::getImmediateMacroName(Loc, Context.getSourceManager(),
                                              Context.getLangOpts());
 
   // Add an empty space at the end as a padding to prevent
   // that macro names concatenate to the names of other macros.
   MacroStack << " ";
 }
 
-/// \brief Returns a string that represents all macro expansions that
-///        expanded into the given SourceLocation.
+/// Returns a string that represents all macro expansions that expanded into the
+/// given SourceLocation.
 ///
 /// If 'getMacroStack(A) == getMacroStack(B)' is true, then the SourceLocations
 /// A and B are expanded from the same macros in the same order.
 static std::string getMacroStack(SourceLocation Loc, ASTContext &Context) {
   std::string MacroStack;
   llvm::raw_string_ostream MacroStackStream(MacroStack);
   SourceManager &SM = Context.getSourceManager();
 
   // Iterate over all macros that expanded into the given SourceLocation.
   while (Loc.isMacroID()) {
     // Add the macro name to the stream.
     printMacroName(MacroStackStream, Context, Loc);
     Loc = SM.getImmediateMacroCallerLoc(Loc);
   }
   MacroStackStream.flush();
   return MacroStack;
 }
 
 namespace {
-/// \brief Collects the data of a single Stmt.
+typedef unsigned DataPiece;
+
+/// 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.
 ///
 /// All collected data is forwarded to the given data consumer of the type T.
 /// The data consumer class needs to provide a member method with the signature:
 ///   update(StringRef Str)
 template <typename T>
 class StmtDataCollector : public ConstStmtVisitor<StmtDataCollector<T>> {
 
   ASTContext &Context;
-  /// \brief The data sink to which all data is forwarded.
+  /// The data sink to which all data is forwarded.
   T &DataConsumer;
 
 public:
-  /// \brief Collects data of the given Stmt.
+  /// Collects data of the given Stmt.
   /// \param S The given statement.
   /// \param Context The ASTContext of S.
   /// \param DataConsumer The data sink to which all data is forwarded.
   StmtDataCollector(const Stmt *S, ASTContext &Context, T &DataConsumer)
       : Context(Context), DataConsumer(DataConsumer) {
     this->Visit(S);
   }
 
   // Below are utility methods for appending different data to the vector.
 
-  void addData(CloneDetector::DataPiece Integer) {
+  void addData(DataPiece Integer) {
     DataConsumer.update(
         StringRef(reinterpret_cast<char *>(&Integer), sizeof(Integer)));
   }
 
   void addData(llvm::StringRef Str) { DataConsumer.update(Str); }
 
   void addData(const QualType &QT) { addData(QT.getAsString()); }
 
for (const LambdaCapture &C : S->captures()) {
       if (C.capturesVariable())
         addData(C.getCapturedVar()->getType());
     }
     addData(S->isGenericLambda());
     addData(S->isMutable());
   })
   DEF_ADD_DATA(DeclStmt, {
     auto numDecls = std::distance(S->decl_begin(), S->decl_end());
-    addData(static_cast<CloneDetector::DataPiece>(numDecls));
+    addData(static_cast<DataPiece>(numDecls));
     for (const Decl *D : S->decls()) {
       if (const VarDecl *VD = dyn_cast<VarDecl>(D)) {
         addData(VD->getType());
       }
     }
   })
   DEF_ADD_DATA(AsmStmt, {
     addData(S->isSimple());
#define DEF_ADD_DATA(CLASS, CODE)                                              \
   DEF_ADD_DATA(AttributedStmt, {
     for (const Attr *A : S->getAttrs()) {
       addData(std::string(A->getSpelling()));
     }
   })
 };
 } // end anonymous namespace
 
-namespace {
-/// Generates CloneSignatures for a set of statements and stores the results in
-/// a CloneDetector object.
-class CloneSignatureGenerator {
-
-  CloneDetector &CD;
-  ASTContext &Context;
-
-  /// \brief Generates CloneSignatures for all statements in the given statement
-  /// tree and stores them in the CloneDetector.
-  ///
-  /// \param S The root of the given statement tree.
-  /// \param ParentMacroStack A string representing the macros that generated
-  ///                         the parent statement or an empty string if no
-  ///                         macros generated the parent statement.
-  ///                         See getMacroStack() for generating such a string.
-  /// \return The CloneSignature of the root statement.
-  CloneDetector::CloneSignature
-  generateSignatures(const Stmt *S, const std::string &ParentMacroStack) {
-    // Create an empty signature that will be filled in this method.
-    CloneDetector::CloneSignature Signature;
+void CloneDetector::analyzeCodeBody(const Decl *D) {
+  assert(D);
+  assert(D->hasBody());
 
-    llvm::MD5 Hash;
+  Sequences.push_back(StmtSequence(D->getBody(), D));
+}
 
-    // Collect all relevant data from S and hash it.
-    StmtDataCollector<llvm::MD5>(S, Context, Hash);
+/// Returns true if and only if \p Stmt contains at least one other
+/// sequence in the \p Group.
+static bool containsAnyInGroup(StmtSequence &Seq,
+                               CloneDetector::CloneGroup &Group) {
+  for (StmtSequence &GroupSeq : Group) {
+    if (Seq.contains(GroupSeq))
+      return true;
+  }
+  return false;
+}
 
-    // Look up what macros expanded into the current statement.
-    std::string StartMacroStack = getMacroStack(S->getLocStart(), Context);
-    std::string EndMacroStack = getMacroStack(S->getLocEnd(), Context);
+/// Returns true if and only if all sequences in \p OtherGroup are
+/// contained by a sequence in \p Group.
+static bool containsGroup(CloneDetector::CloneGroup &Group,
+                          CloneDetector::CloneGroup &OtherGroup) {
+  // We have less sequences in the current group than we have in the other,
+  // so we will never fulfill the requirement for returning true. This is only
+  // possible because we know that a sequence in Group can contain at most
+  // one sequence in OtherGroup.
+  if (Group.size() < OtherGroup.size())
+    return false;
 
-    // First, check if ParentMacroStack is not empty which means we are currently
-    // dealing with a parent statement which was expanded from a macro.
-    // If this parent statement was expanded from the same macros as this
-    // statement, we reduce the initial complexity of this statement to zero.
-    // This causes that a group of statements that were generated by a single
-    // macro expansion will only increase the total complexity by one.
-    // Note: This is not the final complexity of this statement as we still
-    // add the complexity of the child statements to the complexity value.
-    if (!ParentMacroStack.empty() && (StartMacroStack == ParentMacroStack &&
-                                      EndMacroStack == ParentMacroStack)) {
-      Signature.Complexity = 0;
-    }
+  for (StmtSequence &Stmt : Group) {
+    if (!containsAnyInGroup(Stmt, OtherGroup))
+      return false;
+  }
+  return true;
 
-    // Storage for the signatures of the direct child statements. This is only
-    // needed if the current statement is a CompoundStmt.
-    std::vector<CloneDetector::CloneSignature> ChildSignatures;
-    const CompoundStmt *CS = dyn_cast<const CompoundStmt>(S);
+void OnlyLargestCloneConstraint::constrain(
+    std::vector<CloneDetector::CloneGroup> &Result) {
+  std::vector<unsigned> IndexesToRemove;
 
-    // The signature of a statement includes the signatures of its children.
-    // Therefore we create the signatures for every child and add them to the
-    // current signature.
-    for (const Stmt *Child : S->children()) {
-      // Some statements like 'if' can have nullptr children that we will skip.
-      if (!Child)
+  // 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
+  // function from this loop to minimize the performance impact.
+  for (unsigned i = 0; i < Result.size(); ++i) {
+    for (unsigned j = 0; j < Result.size(); ++j) {
+      // Don't compare a group with itself.
+      if (i == j)
         continue;
 
-      // Recursive call to create the signature of the child statement. This
-      // will also create and store all clone groups in this child statement.
-      // We pass only the StartMacroStack along to keep things simple.
-      auto ChildSignature = generateSignatures(Child, StartMacroStack);
-
-      // Add the collected data to the signature of the current statement.
-      Signature.Complexity += ChildSignature.Complexity;
-      Hash.update(StringRef(reinterpret_cast<char *>(&ChildSignature.Hash),
-                            sizeof(ChildSignature.Hash)));
-
-      // If the current statement is a CompoundStatement, we need to store the
-      // signature for the generation of the sub-sequences.
-      if (CS)
-        ChildSignatures.push_back(ChildSignature);
-    }
-
-    // If the current statement is a CompoundStmt, we also need to create the
-    // clone groups from the sub-sequences inside the children.
-    if (CS)
-      handleSubSequences(CS, ChildSignatures);
+      if (containsGroup(Result[j], Result[i])) {
+        IndexesToRemove.push_back(i);
+        break;
+      }
+    }
+  }
+
+  // Erasing a list of indexes from the vector should be done with decreasing
+  // indexes. As IndexesToRemove is constructed with increasing values, we just
+  // reverse iterate over it to get the desired order.
+  for (auto I = IndexesToRemove.rbegin(); I != IndexesToRemove.rend(); ++I) {
+    Result.erase(Result.begin() + *I);
+  }
+}
 
-    // Create the final hash code for the current signature.
-    llvm::MD5::MD5Result HashResult;
-    Hash.final(HashResult);
+static size_t createHash(llvm::MD5 &Hash) {
+  size_t HashCode;
+
+  // Create the final hash code for the current Stmt.
 
-    // Copy as much of the generated hash code to the signature's hash code.
-    std::memcpy(&Signature.Hash, &HashResult,
-                std::min(sizeof(Signature.Hash), sizeof(HashResult)));
-
-    // Save the signature for the current statement in the CloneDetector object.
-    CD.add(StmtSequence(S, Context), Signature);
-
-    return Signature;
-  }
-
-  /// \brief Adds all possible sub-sequences in the child array of the given
-  ///        CompoundStmt to the CloneDetector.
-  /// \param CS The given CompoundStmt.
-  /// \param ChildSignatures A list of calculated signatures for each child in
-  ///                        the given CompoundStmt.
-  void handleSubSequences(
-      const CompoundStmt *CS,
-      const std::vector<CloneDetector::CloneSignature> &ChildSignatures) {
+  // Copy as much as possible of the generated hash code to the Stmt's hash
+  // code.
+  std::memcpy(&HashCode, &HashResult,
+              std::min(sizeof(HashCode), sizeof(HashResult)));
 
-    // FIXME: This function has quadratic runtime right now. Check if skipping
-    // this function for too long CompoundStmts is an option.
+  return HashCode;
+}
 
-    // The length of the sub-sequence. We don't need to handle sequences with
-    // the length 1 as they are already handled in CollectData().
-    for (unsigned Length = 2; Length <= CS->size(); ++Length) {
-      // The start index in the body of the CompoundStmt. We increase the
-      // position until the end of the sub-sequence reaches the end of the
-      // CompoundStmt body.
-      for (unsigned Pos = 0; Pos <= CS->size() - Length; ++Pos) {
-        // Create an empty signature and add the signatures of all selected
-        // child statements to it.
-        CloneDetector::CloneSignature SubSignature;
-        llvm::MD5 SubHash;
+size_t RecursiveCloneTypeIIConstraint::saveHash(
+    const Stmt *S, const Decl *D,
+    std::vector<std::pair<size_t, StmtSequence>> &StmtsByHash) {
+  llvm::MD5 Hash;
+  ASTContext &Context = D->getASTContext();
 
-        for (unsigned i = Pos; i < Pos + Length; ++i) {
-          SubSignature.Complexity += ChildSignatures[i].Complexity;
-          size_t ChildHash = ChildSignatures[i].Hash;
+  StmtDataCollector<llvm::MD5>(S, Context, Hash);
 
-          SubHash.update(StringRef(reinterpret_cast<char *>(&ChildHash),
-                                sizeof(ChildHash)));
-        }
+  auto CS = dyn_cast<CompoundStmt>(S);
+  SmallVector<size_t, 8> ChildHashes;
 
-        // Create the final hash code for the current signature.
-        llvm::MD5::MD5Result HashResult;
-        SubHash.final(HashResult);
-
-        // Copy as much of the generated hash code to the signature's hash code.
-        std::memcpy(&SubSignature.Hash, &HashResult,
-                    std::min(sizeof(SubSignature.Hash), sizeof(HashResult)));
-
-        // Save the signature together with the information about what children
-        // sequence we selected.
-        CD.add(StmtSequence(CS, Context, Pos, Pos + Length), SubSignature);
-      }
+  for (const Stmt *Child : S->children()) {
+    if (Child == nullptr) {
+      ChildHashes.push_back(0);
+      continue;
     }
+    size_t ChildHash = saveHash(Child, D, StmtsByHash);
+    Hash.update(
+        StringRef(reinterpret_cast<char *>(&ChildHash), sizeof(ChildHash)));
+    ChildHashes.push_back(ChildHash);
   }
 
-public:
-  explicit CloneSignatureGenerator(CloneDetector &CD, ASTContext &Context)
-      : CD(CD), Context(Context) {}
-
-  /// \brief Generates signatures for all statements in the given function body.
-  void consumeCodeBody(const Stmt *S) { generateSignatures(S, ""); }
-};
-} // end anonymous namespace
-
-void CloneDetector::analyzeCodeBody(const Decl *D) {
-  assert(D);
-  assert(D->hasBody());
-  CloneSignatureGenerator Generator(*this, D->getASTContext());
-  Generator.consumeCodeBody(D->getBody());
+  if (CS) {
+    for (unsigned Length = 2; Length <= CS->size(); ++Length) {
+      for (unsigned Pos = 0; Pos <= CS->size() - Length; ++Pos) {
+        llvm::MD5 Hash;
+        for (unsigned i = Pos; i < Pos + Length; ++i) {
+          size_t ChildHash = ChildHashes[i];
+          Hash.update(StringRef(reinterpret_cast<char *>(&ChildHash),
+                                sizeof(ChildHash)));
         }
-
-void CloneDetector::add(const StmtSequence &S,
-                        const CloneSignature &Signature) {
-  Sequences.push_back(std::make_pair(Signature, S));
+        StmtsByHash.push_back(std::make_pair(
+            createHash(Hash), StmtSequence(CS, D, Pos, Pos + Length)));
       }
-
-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) {
-  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
-/// contained by a sequence in \p Group.
-bool containsGroup(CloneDetector::CloneGroup &Group,
-                   CloneDetector::CloneGroup &OtherGroup) {
-  // We have less sequences in the current group than we have in the other,
-  // so we will never fulfill the requirement for returning true. This is only
-  // possible because we know that a sequence in Group can contain at most
-  // one sequence in OtherGroup.
-  if (Group.Sequences.size() < OtherGroup.Sequences.size())
-    return false;
-
-  for (StmtSequence &Stmt : Group.Sequences) {
-    if (!containsAnyInGroup(Stmt, OtherGroup))
-      return false;
-  }
-  return true;
-}
-} // end anonymous namespace
+  size_t HashCode = createHash(Hash);
+  StmtsByHash.push_back(std::make_pair(HashCode, StmtSequence(S, D)));
+  return HashCode;
 
 namespace {
-/// \brief Wrapper around FoldingSetNodeID that it can be used as the template
-///        argument of the StmtDataCollector.
+/// Wrapper around FoldingSetNodeID that it can be used as the template
+/// argument of the StmtDataCollector.
 class FoldingSetNodeIDWrapper {
 
   llvm::FoldingSetNodeID &FS;
 
 public:
   FoldingSetNodeIDWrapper(llvm::FoldingSetNodeID &FS) : FS(FS) {}
 
   void update(StringRef Str) { FS.AddString(Str); }
 };
 } // end anonymous namespace
 
-/// \brief Writes the relevant data from all statements and child statements
-///        in the given StmtSequence into the given FoldingSetNodeID.
+/// Writes the relevant data from all statements and child statements
+/// in the given StmtSequence into the given FoldingSetNodeID.
 static void CollectStmtSequenceData(const StmtSequence &Sequence,
                                     FoldingSetNodeIDWrapper &OutputData) {
   for (const Stmt *S : Sequence) {
     StmtDataCollector<FoldingSetNodeIDWrapper>(S, Sequence.getASTContext(),
                                                OutputData);
 
     for (const Stmt *Child : S->children()) {
       if (!Child)
         continue;
 
-      CollectStmtSequenceData(StmtSequence(Child, Sequence.getASTContext()),
+      CollectStmtSequenceData(StmtSequence(Child, Sequence.getContainingDecl()),
                               OutputData);
     }
   }
 }
 
-/// \brief Returns true if both sequences are clones of each other.
+/// Returns true if both sequences are clones of each other.
 static bool areSequencesClones(const StmtSequence &LHS,
                                const StmtSequence &RHS) {
   // We collect the data from all statements in the sequence as we did before
   // when generating a hash value for each sequence. But this time we don't
   // hash the collected data and compare the whole data set instead. This
   // prevents any false-positives due to hash code collisions.
   llvm::FoldingSetNodeID DataLHS, DataRHS;
   FoldingSetNodeIDWrapper LHSWrapper(DataLHS);
   FoldingSetNodeIDWrapper RHSWrapper(DataRHS);
 
   CollectStmtSequenceData(LHS, LHSWrapper);
   CollectStmtSequenceData(RHS, RHSWrapper);
 
   return DataLHS == DataRHS;
 }
 
-/// \brief Finds all actual clone groups in a single group of presumed clones.
-/// \param Result Output parameter to which all found groups are added.
-/// \param Group A group of presumed clones. The clones are allowed to have a
-///              different variable pattern and may not be actual clones of each
-///              other.
-/// \param CheckVariablePattern If true, every clone in a group that was added
-///              to the output follows the same variable pattern as the other
-///              clones in its group.
-static void createCloneGroups(std::vector<CloneDetector::CloneGroup> &Result,
-                              const CloneDetector::CloneGroup &Group,
-                              bool CheckVariablePattern) {
-  // 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.Signature);
-
-    // 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 the sequence doesn't fit to the prototype, we have encountered
-      // an unintended hash code collision and we skip it.
-      if (!areSequencesClones(Prototype, *I)) {
-        ++I;
-        continue;
-      }
+void RecursiveCloneTypeIIConstraint::constrain(
+    std::vector<CloneDetector::CloneGroup> &Sequences) {
+  // FIXME: Maybe we can do this in-place and don't need this additional vector.
+  std::vector<CloneDetector::CloneGroup> Result;
 
-      // If we weren't asked to check for a matching variable pattern in clone
-      // groups we can add the sequence now to the new clone group.
-      // If we were asked to check for matching variable pattern, we first have
-      // to check that there are no differences between the two patterns and
-      // only proceed if they match.
-      if (!CheckVariablePattern ||
-          VariablePattern(*I).countPatternDifferences(PrototypeFeatures) == 0) {
-        FilteredGroup.Sequences.push_back(*I);
-        I = UnassignedSequences.erase(I);
-        continue;
-      }
+  for (CloneDetector::CloneGroup &Group : Sequences) {
+    // We assume in the following code that the Group is non-empty, so we
+    // skip all empty groups.
+    if (Group.empty())
 
-      // We didn't found a matching variable pattern, so we continue with the
-      // next sequence.
-      ++I;
-    }
+    std::vector<std::pair<size_t, StmtSequence>> StmtsByHash;
 
-    // Add a valid clone group to the list of found clone groups.
-    if (!FilteredGroup.isValid())
-      continue;
-
-    Result.push_back(FilteredGroup);
-  }
+    // Generate hash codes for all children of S and save them in StmtsByHash.
+    for (const StmtSequence &S : Group) {
+      saveHash(S.front(), S.getContainingDecl(), StmtsByHash);
     }
 
-void CloneDetector::findClones(std::vector<CloneGroup> &Result,
-                               unsigned MinGroupComplexity,
-                               bool CheckPatterns) {
-  // A shortcut (and necessary for the for-loop later in this function).
-  if (Sequences.empty())
-    return;
-
-  // We need to search for groups of StmtSequences with the same hash code to
-  // create our initial clone groups. By sorting all known StmtSequences by
-  // their hash value we make sure that StmtSequences with the same hash code
-  // are grouped together in the Sequences vector.
-  // Note: We stable sort here because the StmtSequences are added in the order
-  // in which they appear in the source file. We want to preserve that order
-  // because we also want to report them in that order in the CloneChecker.
-  std::stable_sort(Sequences.begin(), Sequences.end(),
-                   [](std::pair<CloneSignature, StmtSequence> LHS,
-                      std::pair<CloneSignature, StmtSequence> RHS) {
-                     return LHS.first.Hash < RHS.first.Hash;
+    // Sort hash_codes in StmtsByHash.
+    std::stable_sort(StmtsByHash.begin(), StmtsByHash.end(),
+                     [this](std::pair<size_t, StmtSequence> LHS,
+                            std::pair<size_t, StmtSequence> RHS) {
+                       return LHS.first < RHS.first;
                      });
 
-  std::vector<CloneGroup> CloneGroups;
-
-  // Check for each CloneSignature if its successor has the same hash value.
-  // We don't check the last CloneSignature as it has no successor.
-  // Note: The 'size - 1' in the condition is safe because we check for an empty
-  // Sequences vector at the beginning of this function.
-  for (unsigned i = 0; i < Sequences.size() - 1; ++i) {
-    const auto Current = Sequences[i];
-    const auto Next = Sequences[i + 1];
+    // Check for each StmtSequence if its successor has the same hash value.
+    // We don't check the last StmtSequence as it has no successor.
+    // Note: The 'size - 1 ' in the condition is safe because we check for an
+    // empty Group vector at the beginning of this function.
+    for (unsigned i = 0; i < StmtsByHash.size() - 1; ++i) {
+      const auto Current = StmtsByHash[i];
 
-    if (Current.first.Hash != Next.first.Hash)
-      continue;
-
-    // It's likely that we just found an sequence of CloneSignatures that
+      // It's likely that we just found an sequence of StmtSequences that
       // represent a CloneGroup, so we create a new group and start checking and
-    // adding the CloneSignatures in this sequence.
-    CloneGroup Group;
-    Group.Signature = Current.first;
+      // adding the StmtSequences in this sequence.
+      CloneDetector::CloneGroup NewGroup;
 
-    for (; i < Sequences.size(); ++i) {
-      const auto &Signature = Sequences[i];
+      size_t PrototypeHash = Current.first;
 
+      for (; i < StmtsByHash.size(); ++i) {
         // A different hash value means we have reached the end of the sequence.
-      if (Current.first.Hash != Signature.first.Hash) {
-        // The current Signature could be the start of a new CloneGroup. So we
+        if (PrototypeHash != StmtsByHash[i].first ||
+            !areSequencesClones(StmtsByHash[i].second, Current.second)) {
+          // The current sequence could be the start of a new CloneGroup. So we
           // decrement i so that we visit it again in the outer loop.
           // Note: i can never be 0 at this point because we are just comparing
-        // the hash of the Current CloneSignature with itself in the 'if' above.
+          // the hash of the Current StmtSequence with itself in the 'if' above.
           assert(i != 0);
           --i;
           break;
         }
+        // Same hash value means we should add the StmtSequence to the current
+        // group.
+        NewGroup.push_back(StmtsByHash[i].second);
+      }
 
-      // Skip CloneSignatures that won't pass the complexity requirement.
-      if (Signature.first.Complexity < MinGroupComplexity)
-        continue;
-
-      Group.Sequences.push_back(Signature.second);
-    }
+      // We created a new clone group with matching hash codes and move it to
+      // the result vector.
+      Result.push_back(NewGroup);
+    }
+  }
+  // Sequences is the output parameter, so we copy our result into it.
+  Sequences = Result;
 
-    // There is a chance that we haven't found more than two fitting
-    // CloneSignature because not enough CloneSignatures passed the complexity
-    // requirement. As a CloneGroup with less than two members makes no sense,
-    // we ignore this CloneGroup and won't add it to the result.
-    if (!Group.isValid())
-      continue;
+size_t MinComplexityConstraint::calculateStmtComplexity(
+    const StmtSequence &Seq, const std::string &ParentMacroStack) {
+  if (Seq.empty())
+    return 0;
+
+  size_t Complexity = 1;
+
+  ASTContext &Context = Seq.getASTContext();
+
+  // Look up what macros expanded into the current statement.
+  std::string StartMacroStack = getMacroStack(Seq.getStartLoc(), Context);
+  std::string EndMacroStack = getMacroStack(Seq.getEndLoc(), Context);
+
+  // First, check if ParentMacroStack is not empty which means we are currently
+  // dealing with a parent statement which was expanded from a macro.
+  // If this parent statement was expanded from the same macros as this
+  // statement, we reduce the initial complexity of this statement to zero.
+  // This causes that a group of statements that were generated by a single
+  // macro expansion will only increase the total complexity by one.
+  // Note: This is not the final complexity of this statement as we still
+  // add the complexity of the child statements to the complexity value.
+  if (!ParentMacroStack.empty() && (StartMacroStack == ParentMacroStack &&
+                                    EndMacroStack == ParentMacroStack)) {
+    Complexity = 0;
+  }
 
-    CloneGroups.push_back(Group);
-  }
+  // Iterate over the Stmts in the StmtSequence and add their complexity values
+  // to the current complexity value.
+  if (Seq.holdsSequence()) {
+    for (const Stmt *S : Seq) {
+      Complexity += calculateStmtComplexity(
+          StmtSequence(S, Seq.getContainingDecl()), StartMacroStack);
+    }
+  } else {
+    for (const Stmt *S : Seq.front()->children()) {
+      Complexity += calculateStmtComplexity(
+          StmtSequence(S, Seq.getContainingDecl()), StartMacroStack);
+    }
+  }
+  return Complexity;
 
-  // Add every valid clone group that fulfills the complexity requirement.
-  for (const CloneGroup &Group : CloneGroups) {
-    createCloneGroups(Result, Group, CheckPatterns);
-  }
+void MatchingVariablePatternConstraint::constrain(
+    std::vector<CloneDetector::CloneGroup> &CloneGroups) {
+  CloneConstraint::splitCloneGroups(
+      CloneGroups, [](const StmtSequence &A, const StmtSequence &B) {
+        VariablePattern PatternA(A);
+        VariablePattern PatternB(B);
+        return PatternA.countPatternDifferences(PatternB) == 0;
+      });
 
-  std::vector<unsigned> IndexesToRemove;
+void CloneConstraint::splitCloneGroups(
+    std::vector<CloneDetector::CloneGroup> &CloneGroups,
+    std::function<bool(const StmtSequence &, const StmtSequence &)> Compare) {
+  std::vector<CloneDetector::CloneGroup> Result;
+  for (auto &HashGroup : CloneGroups) {
+    // Contains all indexes in HashGroup that were already added to a
+    // CloneGroup.
+    std::vector<char> Indexes;
+    Indexes.resize(HashGroup.size());
 
-  // 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
-  // function from this loop to minimize the performance impact.
-  for (unsigned i = 0; i < Result.size(); ++i) {
-    for (unsigned j = 0; j < Result.size(); ++j) {
-      // Don't compare a group with itself.
-      if (i == j)
+    for (unsigned i = 0; i < HashGroup.size(); ++i) {
+      // Skip indexes that are already part of a CloneGroup.
+      if (Indexes[i])
         continue;
 
-      if (containsGroup(Result[j], Result[i])) {
-        IndexesToRemove.push_back(i);
-        break;
+      // Pick the first unhandled StmtSequence and consider it as the
+      // beginning
+      // of a new CloneGroup for now.
+      // We don't add i to Indexes because we never iterate back.
+      StmtSequence Prototype = HashGroup[i];
+      CloneDetector::CloneGroup PotentialGroup = {Prototype};
+      ++Indexes[i];
+
+      // Check all following StmtSequences for clones.
+      for (unsigned j = i + 1; j < HashGroup.size(); ++j) {
+        // Skip indexes that are already part of a CloneGroup.
+        if (Indexes[j])
+          continue;
+
+        // If a following StmtSequence belongs to our CloneGroup, we add it to
+        // it.
+        const StmtSequence &Candidate = HashGroup[j];
+
+        if (!Compare(Prototype, Candidate))
+          continue;
+
+        PotentialGroup.push_back(Candidate);
+        // Make sure we never visit this StmtSequence again.
+        ++Indexes[j];
       }
-    }
-  }
+
+      // Otherwise, add it to the result and continue searching for more
+      // groups.
+      Result.push_back(PotentialGroup);
+    }
+
+    assert(std::all_of(Indexes.begin(), Indexes.end(),
+                       [](char c) { return c == 1; }));
+  CloneGroups = Result;
 
-  // Erasing a list of indexes from the vector should be done with decreasing
-  // indexes. As IndexesToRemove is constructed with increasing values, we just
-  // reverse iterate over it to get the desired order.
-  for (auto I = IndexesToRemove.rbegin(); I != IndexesToRemove.rend(); ++I) {
-    Result.erase(Result.begin() + *I);
+void VariablePattern::addVariableOccurence(const VarDecl *VarDecl,
+                                           const Stmt *Mention) {
+  // 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, Mention);
+      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(), Mention);
+  Variables.push_back(VarDecl);
+}
 
-void CloneDetector::findSuspiciousClones(
-    std::vector<CloneDetector::SuspiciousClonePair> &Result,
-    unsigned MinGroupComplexity) {
-  std::vector<CloneGroup> Clones;
-  // Reuse the normal search for clones but specify that the clone groups don't
-  // need to have a common referenced variable pattern so that we can manually
-  // search for the kind of pattern errors this function is supposed to find.
-  findClones(Clones, MinGroupComplexity, false);
-
-  for (const CloneGroup &Group : Clones) {
-    for (unsigned i = 0; i < Group.Sequences.size(); ++i) {
-      VariablePattern PatternA(Group.Sequences[i]);
-
-      for (unsigned j = i + 1; j < Group.Sequences.size(); ++j) {
-        VariablePattern PatternB(Group.Sequences[j]);
-
-        CloneDetector::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).
-        // TODO: 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) {
-          Result.push_back(ClonePair);
-          break;
-        }
-      }
-    }
+void VariablePattern::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, D);
+
+  // Recursively check all children of the given statement.
+  for (const Stmt *Child : S->children()) {
+    addVariables(Child);
+
+unsigned VariablePattern::countPatternDifferences(
+    const VariablePattern &Other,
+    VariablePattern::SuspiciousClonePair *FirstMismatch) {
+  unsigned NumberOfDifferences = 0;
+
+  assert(Other.Occurences.size() == Occurences.size());
+  for (unsigned i = 0; i < Occurences.size(); ++i) {
+    auto ThisOccurence = Occurences[i];
+    auto OtherOccurence = Other.Occurences[i];
+    if (ThisOccurence.KindID == OtherOccurence.KindID)
+      continue;
+
+    ++NumberOfDifferences;
+
+    // If FirstMismatch is not a nullptr, we need to store information about
+    // the first difference between the two patterns.
+    if (FirstMismatch == nullptr)
+      continue;
+
+    // Only proceed if we just found the first difference as we only store
+    // information about the first difference.
+    if (NumberOfDifferences != 1)
+      continue;
+
+    const VarDecl *FirstSuggestion = nullptr;
+    // If there is a variable available in the list of referenced variables
+    // which wouldn't break the pattern if it is used in place of the
+    // current variable, we provide this variable as the suggested fix.
+    if (OtherOccurence.KindID < Variables.size())
+      FirstSuggestion = Variables[OtherOccurence.KindID];
+
+    // Store information about the first clone.
+    FirstMismatch->FirstCloneInfo =
+        VariablePattern::SuspiciousClonePair::SuspiciousCloneInfo(
+            Variables[ThisOccurence.KindID], ThisOccurence.Mention,
+            FirstSuggestion);
+
+    // Same as above but with the other clone. We do this for both clones as
+    // we don't know which clone is the one containing the unintended
+    // pattern error.
+    const VarDecl *SecondSuggestion = nullptr;
+    if (ThisOccurence.KindID < Other.Variables.size())
+      SecondSuggestion = Other.Variables[ThisOccurence.KindID];
+
+    // Store information about the second clone.
+    FirstMismatch->SecondCloneInfo =
+        VariablePattern::SuspiciousClonePair::SuspiciousCloneInfo(
+            Other.Variables[OtherOccurence.KindID], OtherOccurence.Mention,
+            SecondSuggestion);
+
+    // SuspiciousClonePair guarantees that the first clone always has a
+    // suggested variable associated with it. As we know that one of the two
+    // clones in the pair always has suggestion, we swap the two clones
+    // in case the first clone has no suggested variable which means that
+    // the second clone has a suggested variable and should be first.
+    if (!FirstMismatch->FirstCloneInfo.Suggestion)
+      std::swap(FirstMismatch->FirstCloneInfo, FirstMismatch->SecondCloneInfo);
+
+    // This ensures that we always have at least one suggestion in a pair.
+    assert(FirstMismatch->FirstCloneInfo.Suggestion);
   }
+
+  return NumberOfDifferences;
 }

cfe/trunk/lib/StaticAnalyzer/Checkers/CloneChecker.cpp

 
 public:
   void checkASTCodeBody(const Decl *D, AnalysisManager &Mgr,
                         BugReporter &BR) const;
 
   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
 
 void CloneChecker::checkASTCodeBody(const Decl *D, AnalysisManager &Mgr,
                                     BugReporter &BR) const {
   // Every statement that should be included in the search for clones needs to
   // be passed to the CloneDetector.
   Detector.analyzeCodeBody(D);
void CloneChecker::checkEndOfTranslationUnit(const TranslationUnitDecl *TU,
   assert(MinComplexity >= 0);
 
   bool ReportSuspiciousClones = Mgr.getAnalyzerOptions().getBooleanOption(
       "ReportSuspiciousClones", true, this);
 
   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;
+
+  // 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));
 
-  if (ReportNormalClones)
-    reportClones(BR, Mgr, MinComplexity);
+  reportClones(BR, Mgr, AllCloneGroups);
 }
 
 static PathDiagnosticLocation makeLocation(const StmtSequence &S,
                                            AnalysisManager &Mgr) {
   ASTContext &ACtx = Mgr.getASTContext();
   return PathDiagnosticLocation::createBegin(
       S.front(), ACtx.getSourceManager(),
       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(
         new BugType(this, "Suspicious code clone", "Code clone"));
 
   ASTContext &ACtx = BR.getContext();
   SourceManager &SM = ACtx.getSourceManager();
   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.
     // Think how to perform more accurate suggestions?
 
     auto R = llvm::make_unique<BugReport>(
         *BT_Suspicious,
         "Potential copy-paste error; did you really mean to use '" +

cfe/trunk/unittests/Analysis/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   Support
   )
 
-add_clang_unittest(CFGTests
+add_clang_unittest(ClangAnalysisTests
   CFGTest.cpp
+  CloneDetectionTest.cpp
   )
 
-target_link_libraries(CFGTests
+target_link_libraries(ClangAnalysisTests
   clangAnalysis
   clangAST
   clangASTMatchers
   clangBasic
   clangFrontend
   clangTooling
   )

cfe/trunk/unittests/Analysis/CloneDetectionTest.cpp

+//===- unittests/Analysis/CloneDetectionTest.cpp - Clone detection tests --===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/AST/RecursiveASTVisitor.h"
+#include "clang/Analysis/CloneDetection.h"
+#include "clang/Tooling/Tooling.h"
+#include "gtest/gtest.h"
+
+namespace clang {
+namespace analysis {
+namespace {
+
+class CloneDetectionVisitor
+    : public RecursiveASTVisitor<CloneDetectionVisitor> {
+
+  CloneDetector &Detector;
+
+public:
+  explicit CloneDetectionVisitor(CloneDetector &D) : Detector(D) {}
+
+  bool VisitFunctionDecl(FunctionDecl *D) {
+    Detector.analyzeCodeBody(D);
+    return true;
+  }
+};
+
+/// Example constraint for testing purposes.
+/// Filters out all statements that are in a function which name starts with
+/// "bar".
+class NoBarFunctionConstraint {
+public:
+  void constrain(std::vector<CloneDetector::CloneGroup> &CloneGroups) {
+    CloneConstraint::splitCloneGroups(
+        CloneGroups, [](const StmtSequence &A, const StmtSequence &B) {
+          // Check if one of the sequences is in a function which name starts
+          // with "bar".
+          for (const StmtSequence &Arg : {A, B}) {
+            if (const auto *D =
+                    dyn_cast<const FunctionDecl>(Arg.getContainingDecl())) {
+              if (D->getNameAsString().find("bar") == 0)
+                return false;
+            }
+          }
+          return true;
+        });
+  }
+};
+
+TEST(CloneDetector, FilterFunctionsByName) {
+  auto ASTUnit =
+      clang::tooling::buildASTFromCode("void foo1(int &a1) { a1++; }\n"
+                                       "void foo2(int &a2) { a2++; }\n"
+                                       "void bar1(int &a3) { a3++; }\n"
+                                       "void bar2(int &a4) { a4++; }\n");
+  auto TU = ASTUnit->getASTContext().getTranslationUnitDecl();
+
+  CloneDetector Detector;
+  // Push all the function bodies into the detector.
+  CloneDetectionVisitor Visitor(Detector);
+  Visitor.TraverseTranslationUnitDecl(TU);
+
+  // Find clones with the usual settings, but but we want to filter out
+  // all statements from functions which names start with "bar".
+  std::vector<CloneDetector::CloneGroup> CloneGroups;
+  Detector.findClones(CloneGroups, NoBarFunctionConstraint(),
+                      RecursiveCloneTypeIIConstraint(),
+                      MinComplexityConstraint(2), MinGroupSizeConstraint(2),
+                      OnlyLargestCloneConstraint());
+
+  ASSERT_EQ(CloneGroups.size(), 1u);
+  ASSERT_EQ(CloneGroups.front().size(), 2u);
+
+  for (auto &Clone : CloneGroups.front()) {
+    const auto ND = dyn_cast<const FunctionDecl>(Clone.getContainingDecl());
+    ASSERT_TRUE(ND != nullptr);
+    // Check that no function name starting with "bar" is in the results...
+    ASSERT_TRUE(ND->getNameAsString().find("bar") != 0);
+  }
+
+  // Retry above's example without the filter...
+  CloneGroups.clear();
+
+  Detector.findClones(CloneGroups, RecursiveCloneTypeIIConstraint(),
+                      MinComplexityConstraint(2), MinGroupSizeConstraint(2),
+                      OnlyLargestCloneConstraint());
+  ASSERT_EQ(CloneGroups.size(), 1u);
+  ASSERT_EQ(CloneGroups.front().size(), 4u);
+
+  // Count how many functions with the bar prefix we have in the results.
+  int FoundFunctionsWithBarPrefix = 0;
+  for (auto &Clone : CloneGroups.front()) {
+    const auto ND = dyn_cast<const FunctionDecl>(Clone.getContainingDecl());
+    ASSERT_TRUE(ND != nullptr);
+    // This time check that we picked up the bar functions from above
+    if (ND->getNameAsString().find("bar") == 0) {
+      FoundFunctionsWithBarPrefix++;
+    }
+  }
+  // We should have found the two functions bar1 and bar2.
+  ASSERT_EQ(FoundFunctionsWithBarPrefix, 2);
+}
+} // namespace
+} // namespace analysis
+} // namespace clang