Added basic capabilities to detect source code clones.

[teemperor]

Summary

This patch adds the CloneDetector class which allows searching source code for clones.

CloneDetector processes translation units and generates search data for each statement in a translation unit.
Afterwards, it can search for clones based on the generated data.

The way CloneDetector searches for clones relies on a locality-sensitive hash functions that accepts
clang::Stmt* as an input and outputs integer hash values. The generated hash values are generated
in a way that produces identical hash values for similar statements.

Before searching, CloneDetector hashes each statement and stores the hash value.
These hash values are then searched for identical values during the actual clone search and the
related statements are then assumed to be clones of each other.

This initial patch only provides a simple hashing mechanism that hashes the class type of each
statement. Hashing class specific data will be added in future patches.

Also, a simple checker is provided to test the CloneDetector class with normal regression test files.
This checker searches the current translation unit for clones using the CloneDetector class and reports them.

[zaks.anna]

Please, pull out the refactor into a separate commit and ask someone who often reviews SemaChecking review it.

lib/AST/CMakeLists.txt

10 ↗

(On Diff #58975)

Do we want this code to live in the AST library? Who will be the users of this?

[v.g.vassilev]

include/clang/Basic/SourceManager.h

1173 ↗

(On Diff #58975)

A leftover from something else?

1179 ↗

(On Diff #58975)

Could you revise the grammar of this entire sentence?

lib/AST/ASTStructure.cpp

42 ↗

(On Diff #58975)

You meant "now" instead of "know"?

88 ↗

(On Diff #58975)

I'd add the SourceManager as a member and shorten this code snippet.

93 ↗

(On Diff #58975)

You meant "as not to be"?

100 ↗

(On Diff #58975)

Is that the LLVM/Clang common notion for documenting private members: (i.e. doxygen disabled) instead of /

146 ↗

(On Diff #58975)

Why this is dangling? Also "reset".

202 ↗

(On Diff #58975)

Maybe we should issue a warning about it.

366 ↗

(On Diff #58975)

Could we document these "magic" prime numbers and move them in a central place. I think this would make it more readable.

404 ↗

(On Diff #58975)

Could the implementation of GCCAsmStmt go here in the base class? And GCCAsmStmt to fall back to the base class (I assume this way we would have basic support for MSAsmStmt). This holds for the other cases of this pattern, eg.: *Literal.

unittests/AST/ASTStructureTest.cpp

46 ↗

(On Diff #58975)

Why not passing just the ASTContext variable?

80 ↗

(On Diff #58975)

Same copy-paste here ;) See above.

103 ↗

(On Diff #58975)

I'd move this up and reuse the variables in the rhs of HashA and HashB.

130 ↗

(On Diff #58975)

What we will get from compareStmt("if (1 == 2) {}", "if (false) {}")

[teemperor]

• Patch now only provides basic generic hashing and is smaller.
• Code style is now respecting LLVM/clang guidelines.
• Documented all non-trivial functions.
• Moved testing from unittests to normal tests.
• Added tests for false-positives.
• Fixed the problems pointed out by Vassil (beside "Is that the LLVM/Clang common notion for documenting private members: (i.e. doxygen disabled) instead of /").
• No longer patching SourceManager.h.

[teemperor]

• Using doxygen-style comments for all private members.

[teemperor]

• Fixed a few typos in comments and documentation.

[v.g.vassilev]

include/clang/AST/CloneDetection.h

148 ↗

(On Diff #62899)

It might be a good idea to detect cloned comments, too.

153 ↗

(On Diff #62899)

Can you move this on the previous line?

166 ↗

(On Diff #62899)

This should go on prev line too. Please check all comments for this pattern.

215 ↗

(On Diff #62899)

We shouldn't copy (or hope this would be std::moved). Can you pass it as a reference to the argument list?

lib/AST/CloneDetection.cpp

22 ↗

(On Diff #62899)

It is a very common pattern in clang the ASTContext to be passed as ASTContext&, this should simplify the body of the constructors.

45 ↗

(On Diff #62899)

I'd factor out the Context->getSourceManager() in a local variable.

54 ↗

(On Diff #62899)

I am not sure what is the intent but shouldn't that be Stmt const* const*?

56 ↗

(On Diff #62899)

Please use auto CS = cast<CompoundStmt>(S);

This logic will crash on void f() try {} catch(...){} In this case we do not generate a CompoundStmt.

64 ↗

(On Diff #62899)

Same as above.

84 ↗

(On Diff #62899)

Still a floating magic constant. Could you factor it out in a variable with a meaningful name?

112 ↗

(On Diff #62899)

Doxygen style /// ?

139 ↗

(On Diff #62899)

Could we use a range-based for loop. This looks odd.

161 ↗

(On Diff #62899)

Indent.

164 ↗

(On Diff #62899)

Could you move these members above. I don't think this is common in the codebase.

293 ↗

(On Diff #62899)

Capital letters are more common when naming iterators. What about small i and j here. And down you can use I and you won't need to break the line.

[teemperor]

• Fixed the problems pointed out by Vassil (Thanks!)
• Comments now have less line breaks.
• Added more documentation to HashValue, it's hash function and the used prime numbers.
• Added a typedef for StmtSequence::iterator.
• StmtSequence::end() is now always returning a correct iterator.

[teemperor]

• Fixed type of StmtSequence::iterator.

[teemperor]

• StmtSequence is now treating all Stmt objects as const.

[zaks.anna]

Hi,

Thank you for working on this!

Here are several comments from a partial review.

Can you talk a bit about how do you envision to generalize this to copy and paste detection, where the pasted code is only partially modified? Do you think this could be generalized in that way?

include/clang/AST/CloneDetection.h

20 ↗

(On Diff #63266)

Please, check if there are better data structures you could be using: http://llvm.org/docs/ProgrammersManual.html#map-like-containers-std-map-densemap-etc

131 ↗

(On Diff #63266)

We are comparing the Stmt pointers here. Does this make results non-deterministic?

145 ↗

(On Diff #63266)

Let's not talk about multiple TU here since much more is needed to support them. Maybe we should just say that, first, given a TU, the class generates the clone identifiers (hashes?) of statements in it (by running AnalyzeTranslationUnitDecl)?

The description of the method already states that it can be called multiple times.

161 ↗

(On Diff #63266)

StmtData is too generic of a name. Maybe it could be called something like code signature, clone signature, or code hash?

166 ↗

(On Diff #63266)

serves -> serve

186 ↗

(On Diff #63266)

Could this return an llvm Optional instead of the error code?

201 ↗

(On Diff #63266)

database -> map?

I would just say "Stores the StmtSequence with its associated data to allow future querying."

209 ↗

(On Diff #63266)

Please, do not talk about "all translation units" here. Maybe say something like previously seen/stored statements/code or something like that.

217 ↗

(On Diff #63266)

Make 10 into a constant. It probably should be a checker parameter.

include/clang/StaticAnalyzer/Checkers/Checkers.td

668 ↗

(On Diff #63266)

This should be an "alpha" package until it's considered to be ready for end users.

lib/AST/CMakeLists.txt

10 ↗

(On Diff #63266)

Again, I do not think this should be in the AST. Who the users of this will be? If you envision users outside of Clang Static Analyzer, maybe we could add this to lib/Analysis/.

lib/AST/CloneDetection.cpp

56 ↗

(On Diff #63266)

http://llvm.org/docs/CodingStandards.html#use-early-exits-and-continue-to-simplify-code

103 ↗

(On Diff #63266)

This should probably be a utility instead of something specific to this checker. Do we have something similar to this in LLVM already?

lib/StaticAnalyzer/Checkers/CloneChecker.cpp

45 ↗

(On Diff #63266)

Is it possible to report these through BugReporter?

[NoQ]

Your code is well-written and easy to understand, and makes me want to use it on my code! Added some minor comments, and there seems to be a small logic error in the compound statement hasher.

Not sure if that was already explained in detail, but i seem to agree that the only point for this project to integrate into Clang Static Analyzer is to integrate with the BugReporter facility - at least optionally: it would allow the reports of the clone detector checker to be gathered and viewed in a manner similar to other checkers - i.e. through scan-build/scan-view, probably CodeChecker and other tools. That should make the check easier to run and attract more users. However, the BugReporter mechanism is tweaked for the analyzer's path-sensitive checkers, so it'd need to be modified to suit your purpose, so in my opinion this is not critical for the initial commit.

lib/AST/CloneDetection.cpp

52 ↗

(On Diff #63266)

Perhaps we could early-return when we see that StartIsInBounds is false (for performance, because isBeforeInTranslationUnit looks heavy).

88 ↗

(On Diff #63266)

It seems that the last index is off-by-one, i think you meant something like:

H(D) = PrimeFactor^(N-1) * D[0] + PrimeFactor^(N-2) * D[1] + ... + D[N-1]

175 ↗

(On Diff #63266)

Shouldn't it say something like "EndIterator = StartIterator"? Because when StartPos is non-zero, in your code we get [StartPos, Length) instead of [StartPos, StartPos + Length). In your code, Length acts as some kind of EndPos instead.

194 ↗

(On Diff #63266)

Simplifies to:

StmtSequence ChildSequence(Child, Context);

238 ↗

(On Diff #63266)

I think that the code that deals with computing data for sections of compound statements (as opposed to saving this data) should be moved to VisitStmt(). Or, even better, to VisitCompoundStmt() - that's the whole point of having a visitor, after all. Upon expanding the complexity of the hash, you'd probably provide more special cases for special statement classes, which would all sit in their own Visit method.

That's for the future though, not really critical.

262 ↗

(On Diff #63266)

This code is duplicated from the beginning of the function, which synergizes with my point above: if SaveData() contained only that much, then it could have been re-used on both call sites.

lib/StaticAnalyzer/Checkers/CloneChecker.cpp

40 ↗

(On Diff #63266)

TU->getASTContext().getTranslationUnitDecl() is always equal to TU - there should, in most cases, be only one TranslationUnitDecl object around, but even if there'd be more some day, i think this invariant would still hold.

43 ↗

(On Diff #63266)

An idea: because this function optionally accepts MinGroupComplexity, you may probably want to expose this feature as a checker-specific option - see MallocChecker::IsOptimistic as an example, shouldn't be hard.

45 ↗

(On Diff #63266)

I think that'd require changes in the BugReporter to allow easily adding extra pieces to path-insensitive reports (which is quite a wanted feature in many AST-based checkers - assuming we want more AST-based checkers to be moved into the analyzer specifically for better reporting, integration with scan-build, and stuff like that).

test/Analysis/copypaste/test-min-max.cpp

39 ↗

(On Diff #63266)

Perhaps add a // no-warning comment to spots that should not cause a warning? This comment has no effect on the test suite, just a traditional way to notify the reader.

[teemperor]

• Checker is now in the alpha package and hidden.
• MinGroupComplexity is now a parameter for the checker.
• StmtData is now called CloneSignature.
• Replaced the std::map inside CloneDetector with a vector and a small cache in the HashVisitor.
• Moved code from AST to Analysis.
• Fixed multiple other smaller problems pointed out in the review. (Thanks, Vassil, Anna and Artem!)

[teemperor]

include/clang/AST/CloneDetection.h

131 ↗

(On Diff #63266)

Good point. The updated patch only sorts by deterministic hash values which should fix this.

lib/AST/CMakeLists.txt

10 ↗

(On Diff #63266)

Oh, sorry! I wanted to bring this up in a meeting but it seems I've forgot to do so.

The point with this being in AST is that we might want to merge the Stmt::Profile implementation with the implementation of CloneDtection. And Stmt::Profile is a part of AST AFAIK, so I think we need to stay in the same library? I don't have a good overview over the clang build infrastructure yet, so I would appreciate opinions on that.

If that's something we will handle later, what would be a better place for the code?

lib/AST/CloneDetection.cpp

103 ↗

(On Diff #63266)

Yes, there is similar builtin hashing available in llvm::hashing, but the API is designed to work with iterator pairs. So we either have to record all the data in a vector and hash that (which is what FoldingSetNodeID does) or use code that isn't exposed in the API (llvm::hashing::detail::hash_state). The first option creates unnecessary overhead and the second option would require either patching LLVM or using code that isn't part of the public API.

I updated the patch with something that uses FoldingSetNodeID for now. I'll update it later if we can land a patch in LLVM that adds an API for hashing without recording all necessary data beforehand.

[NoQ]

Regarding the cache stack - it feels easier for me to allocate a separate stack for each statement, and put the stack on stack (!) rather than having it global. This way it'd be automatically cleaned for you when VisitStmt() exits, and you'd be able to address child cache by index rather then through scanning.

lib/Analysis/CloneDetection.cpp

142 ↗

(On Diff #63851)

This calculation happens in linear time and each statement is only visited a
fixed amount of times during this process.

Isn't SaveAllSubSequences() quadratic?

424 ↗

(On Diff #63851)

I suspect that all i's that make it into the IndexesToRemove vector are already unique and increasing, by construction. We take some i, see if we need to remove it, then push it at most once and take (i + 1).

[v.g.vassilev]

LGTM, given the comments are addressed.

include/clang/Analysis/CloneDetection.h

37 ↗

(On Diff #63851)

It is more common in the codebase to use Did you mean const Stmt *S. Could you update all similar occurrences to it?

lib/Analysis/CloneDetection.cpp

119 ↗

(On Diff #63851)

Same here const StmtSequence &S is the common style in the codebase.

[teemperor]

Ok, so I think I've addressed the points from last meeting in this patch:

It was planned to replace custom hashing with FoldingSetNodeID and a hashmap: In this patch I removed all custom hashing. It's now done via LLVM's StringMap and strings which brings the same functionality. Using FoldingSetNodeID is not possible because it hides it's internal data vector which StringMap doesn't support, so I've just used a normal vector instead.

It was also planned to refactor CloneSignatureCache: In this patch I've completely removed the cache because it is no longer necessary. Fixing it was not an option because we assumed that the statements RecursiveASTVisitor visits are the same that Stmt::children() delivers, which is for example for LambdaExprs not true (and RecursiveASTVisitor makes no promise about that in it's API). The only sensible fix for this was to use Artem's initial suggestion to not use RecursiveASTVisitor to traverse statements.

I've also adressed Artems and Vassils comments regarding documentation and code style in this patch (Thanks!).

[teemperor]

include/clang/AST/CloneDetection.h

149 ↗

(On Diff #62877)

Put the idea on the future TODO list, but we probably can't reuse a big part of the current infrastructure for it.

[NoQ]

The idea with strings as keys is curious! I've got a few more minor comments :)

lib/Analysis/CloneDetection.cpp

104 ↗

(On Diff #65291)

Typo: statement.

147 ↗

(On Diff #65291)

Maybe pass ChildSignatures by reference?

178 ↗

(On Diff #65291)

You'd probably want to add ObjCMethodDecl and BlockDecl, because they aren't sub-classes of FunctionDecl (and probably even tests for that).

Because this part of the code essentially re-implements AnalysisConsumer, (a RecursiveASTVisitor that tells us what code bodies to analyze with the static analyzer - i should've looked there earlier!!).

Alternatively, you can just rely on AnalysisConsumer, which would eliminate the recursive visitor completely:

DelegateVisitingToAnalysisConsumer.patch3 KBDownload

This way you'd be analyzing exactly the same code bodies that the analyzer itself would analyze; if you'd want to extend to various declarations, you'd be able to do that by subscribing on check::ASTDecl. But i dare not to predict what kind of different flexibility you'd need next.

188 ↗

(On Diff #65291)

Micro-nit: Capitalize 'V' in 'visitor'?

[teemperor]

• Fixed the minor problems as pointed out by Artem.
• Now using AnalysisConsumer instead of RecursiveASTVisitor.
• Function names are now confirming to LLVM code-style.
• Renamed DataCollectVisitor to CloneSignatureGenerator (as it's no longer following the Visitor pattern).
• Added tests for clone detection in ObjC-methods and blocks.
• Moved false-positive tests into own file.

[teemperor]

• The CloneGroup values in StringMap no longer store a copy of their own key.

[teemperor]

lib/Analysis/CloneDetection.cpp

178 ↗

(On Diff #65291)

Thanks for the patch!

[NoQ]

lib/Analysis/CloneDetection.cpp

148 ↗

(On Diff #65441)

I've a feeling this comment was forgotten :o

[teemperor]

• Now passing ChildSignatures by const reference.

[NoQ]

Great! Will commit.

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

+//===--- CloneDetection.h - Finds code clones in an AST ---------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+///
+/// /file
+/// 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/StringMap.h"
+
+#include <vector>
+
+namespace clang {
+
+class Stmt;
+class Decl;
+class ASTContext;
+class CompoundStmt;
+
+/// \brief 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;
+
+  /// 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.
+  ///
+  /// 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 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);
+
+  /// \brief 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);
+
+  /// \brief 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.
+  iterator end() const;
+
+  /// Returns the first statement in this sequence.
+  ///
+  /// This method should only be called on a non-empty StmtSequence object.
+  const Stmt *front() const {
+    assert(!empty());
+    return begin()[0];
+  }
+
+  /// Returns the last statement in this sequence.
+  ///
+  /// This method should only be called on a non-empty StmtSequence object.
+  const Stmt *back() const {
+    assert(!empty());
+    return begin()[size() - 1];
+  }
+
+  /// Returns the number of statements this object holds.
+  unsigned size() const {
+    if (holdsSequence())
+      return EndIndex - StartIndex;
+    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;
+  }
+
+  /// 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.
+  SourceLocation getStartLoc() const;
+
+  /// Returns the end sourcelocation of the last statement in this sequence.
+  ///
+  /// This method should only be called on a non-empty StmtSequence object.
+  SourceLocation getEndLoc() const;
+
+  bool operator==(const StmtSequence &Other) const {
+    return std::tie(S, StartIndex, EndIndex) ==
+           std::tie(Other.S, Other.StartIndex, Other.EndIndex);
+  }
+
+  bool operator!=(const StmtSequence &Other) const {
+    return std::tie(S, StartIndex, EndIndex) !=
+           std::tie(Other.S, Other.StartIndex, Other.EndIndex);
+  }
+
+  /// 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.
+///
+/// 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 .
+///
+/// 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:
+  /// Holds the data about a StmtSequence that is needed during the search for
+  /// code clones.
+  struct CloneSignature {
+    /// \brief Holds all relevant data of a StmtSequence.
+    ///
+    /// If this variable is equal for two different StmtSequences, then they can
+    /// be considered clones of each other.
+    std::vector<unsigned> Data;
+
+    /// \brief The complexity of the StmtSequence.
+    ///
+    /// This scalar value serves as a simple way of filtering clones that are
+    /// too small to be reported. A greater value indicates that the related
+    /// StmtSequence is probably more interesting to the user.
+    unsigned Complexity;
+
+    /// \brief Creates an empty CloneSignature without any data.
+    CloneSignature() : Complexity(1) {}
+
+    CloneSignature(const std::vector<unsigned> &Data, unsigned Complexity)
+        : Data(Data), Complexity(Complexity) {}
+
+    /// \brief Adds the data from the given CloneSignature to this one.
+    void add(const CloneSignature &Other) {
+      Data.insert(Data.end(), Other.Data.begin(), Other.Data.end());
+      Complexity += Other.Complexity;
+    }
+  };
+
+  /// 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;
+    unsigned Complexity;
+
+    CloneGroup(const StmtSequence &Seq, unsigned Complexity)
+        : Complexity(Complexity) {
+      Sequences.push_back(Seq);
+    }
+
+    /// \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;
+    }
+  };
+
+  /// \brief Generates and stores search data for all statements in the body of
+  ///        the given Decl.
+  void analyzeCodeBody(const Decl *D);
+
+  /// \brief Stores the CloneSignature to allow future querying.
+  void add(const StmtSequence &S, const CloneSignature &Signature);
+
+  /// \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.
+  void findClones(std::vector<CloneGroup> &Result, unsigned MinGroupComplexity);
+
+private:
+  /// Stores all found clone groups including invalid groups with only a single
+  /// statement.
+  std::vector<CloneGroup> CloneGroups;
+  /// Maps search data to its related index in the \p CloneGroups vector.
+  llvm::StringMap<std::size_t> CloneGroupIndexes;
+};
+
+} // end namespace clang
+
+#endif // LLVM_CLANG_AST_CLONEDETECTION_H

cfe/trunk/include/clang/StaticAnalyzer/Checkers/Checkers.td

 def LocalizabilityAlpha : Package<"localizability">, InPackage<CocoaAlpha>;
 def LocalizabilityOptIn : Package<"localizability">, InPackage<CocoaOptIn>;
 
 def MPI : Package<"mpi">, InPackage<OptIn>;
 
 def LLVM : Package<"llvm">;
 def Debug : Package<"debug">;
 
+def CloneDetectionAlpha : Package<"clone">, InPackage<Alpha>, Hidden;
+
 //===----------------------------------------------------------------------===//
 // Core Checkers.
 //===----------------------------------------------------------------------===//
 
 let ParentPackage = Core in {
 
 def DereferenceChecker : Checker<"NullDereference">,
   HelpText<"Check for dereferences of null pointers">,
def ExplodedGraphViewer : Checker<"ViewExplodedGraph">,
   HelpText<"View Exploded Graphs using GraphViz">,
   DescFile<"DebugCheckers.cpp">;
 
 def BugHashDumper : Checker<"DumpBugHash">,
   HelpText<"Dump the bug hash for all statements.">,
   DescFile<"DebugCheckers.cpp">;
 
 } // end "debug"
+
+
+//===----------------------------------------------------------------------===//
+// Clone Detection
+//===----------------------------------------------------------------------===//
+
+let ParentPackage = CloneDetectionAlpha in {
+
+def CloneChecker : Checker<"CloneChecker">,
+  HelpText<"Reports similar pieces of code.">,
+  DescFile<"CloneChecker.cpp">;
+
+} // end "clone"
+

cfe/trunk/lib/Analysis/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   Support
   )
 
 add_clang_library(clangAnalysis
   AnalysisDeclContext.cpp
   BodyFarm.cpp
   CFG.cpp
   CFGReachabilityAnalysis.cpp
   CFGStmtMap.cpp
   CallGraph.cpp
+  CloneDetection.cpp
   CocoaConventions.cpp
   Consumed.cpp
   CodeInjector.cpp
   Dominators.cpp
   FormatString.cpp
   LiveVariables.cpp
   ObjCNoReturn.cpp
   PostOrderCFGView.cpp

cfe/trunk/lib/Analysis/CloneDetection.cpp

+//===--- CloneDetection.cpp - Finds code clones in an AST -------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+///
+///  This file implements classes for searching and anlyzing source code clones.
+///
+//===----------------------------------------------------------------------===//
+
+#include "clang/Analysis/CloneDetection.h"
+
+#include "clang/AST/ASTContext.h"
+#include "clang/AST/RecursiveASTVisitor.h"
+#include "clang/AST/Stmt.h"
+#include "llvm/ADT/StringRef.h"
+
+using namespace clang;
+
+StmtSequence::StmtSequence(const CompoundStmt *Stmt, ASTContext &Context,
+                           unsigned StartIndex, unsigned EndIndex)
+    : S(Stmt), Context(&Context), 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()
+    : S(nullptr), Context(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)
+    return false;
+
+  const SourceManager &SM = Context->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;
+
+  bool EndIsInBounds =
+      SM.isBeforeInTranslationUnit(Other.getEndLoc(), getEndLoc()) ||
+      Other.getEndLoc() == getEndLoc();
+  return EndIsInBounds;
+}
+
+StmtSequence::iterator StmtSequence::begin() const {
+  if (!holdsSequence()) {
+    return &S;
+  }
+  auto CS = cast<CompoundStmt>(S);
+  return CS->body_begin() + StartIndex;
+}
+
+StmtSequence::iterator StmtSequence::end() const {
+  if (!holdsSequence()) {
+    return &S + 1;
+  }
+  auto CS = cast<CompoundStmt>(S);
+  return CS->body_begin() + EndIndex;
+}
+
+SourceLocation StmtSequence::getStartLoc() const {
+  return front()->getLocStart();
+}
+
+SourceLocation StmtSequence::getEndLoc() const { return back()->getLocEnd(); }
+
+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.
+  /// \return The CloneSignature of the root statement.
+  CloneDetector::CloneSignature generateSignatures(const Stmt *S) {
+    // Create an empty signature that will be filled in this method.
+    CloneDetector::CloneSignature Signature;
+
+    // The only relevant data for now is the class of the statement.
+    // TODO: Collect statement class specific data.
+    Signature.Data.push_back(S->getStmtClass());
+
+    // 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);
+
+    // 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)
+        continue;
+
+      // Recursive call to create the signature of the child statement. This
+      // will also create and store all clone groups in this child statement.
+      auto ChildSignature = generateSignatures(Child);
+
+      // Add the collected data to the signature of the current statement.
+      Signature.add(ChildSignature);
+
+      // 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);
+
+    // 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) {
+
+    // FIXME: This function has quadratic runtime right now. Check if skipping
+    // this function for too long CompoundStmts is an option.
+
+    // 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;
+
+        for (unsigned i = Pos; i < Pos + Length; ++i) {
+          SubSignature.add(ChildSignatures[i]);
+        }
+
+        // Save the signature together with the information about what children
+        // sequence we selected.
+        CD.add(StmtSequence(CS, Context, Pos, Pos + Length), SubSignature);
+      }
+    }
+  }
+
+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());
+}
+
+void CloneDetector::add(const StmtSequence &S,
+                        const CloneSignature &Signature) {
+  // StringMap only works with StringRefs, so we create one for our data vector.
+  auto &Data = Signature.Data;
+  StringRef DataRef = StringRef(reinterpret_cast<const char *>(Data.data()),
+                                Data.size() * sizeof(unsigned));
+
+  // Search with the help of the signature if we already have encountered a
+  // clone of the given StmtSequence.
+  auto I = CloneGroupIndexes.find(DataRef);
+  if (I == CloneGroupIndexes.end()) {
+    // We haven't found an existing clone group, so we create a new clone group
+    // for this StmtSequence and store the index of it in our search map.
+    CloneGroupIndexes[DataRef] = CloneGroups.size();
+    CloneGroups.emplace_back(S, Signature.Complexity);
+    return;
+  }
+
+  // We have found an existing clone group and can expand it with the given
+  // StmtSequence.
+  CloneGroups[I->getValue()].Sequences.push_back(S);
+}
+
+namespace {
+/// \brief Returns true if and only if \p Stmt contains at least one other
+/// sequence in the \p Group.
+bool containsAnyInGroup(StmtSequence &Stmt,
+                            CloneDetector::CloneGroup &Group) {
+  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
+
+void CloneDetector::findClones(std::vector<CloneGroup> &Result,
+                               unsigned MinGroupComplexity) {
+  // Add every valid clone group that fulfills the complexity requirement.
+  for (const CloneGroup &Group : CloneGroups) {
+    if (Group.isValid() && Group.Complexity >= MinGroupComplexity) {
+      Result.push_back(Group);
+    }
+  }
+
+  std::vector<unsigned> IndexesToRemove;
+
+  // Compare every group in the result with the rest. If one groups contains
+  // another group, we only need to return the bigger group.
+  // Note: This doesn't scale well, so if possible avoid calling any heavy
+  // 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;
+
+      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);
+  }
+}

cfe/trunk/lib/StaticAnalyzer/Checkers/CMakeLists.txt

add_clang_library(clangStaticAnalyzerCheckers
   CastToStructChecker.cpp
   CheckObjCDealloc.cpp
   CheckObjCInstMethSignature.cpp
   CheckSecuritySyntaxOnly.cpp
   CheckSizeofPointer.cpp
   CheckerDocumentation.cpp
   ChrootChecker.cpp
   ClangCheckers.cpp
+  CloneChecker.cpp
   CXXSelfAssignmentChecker.cpp
   DeadStoresChecker.cpp
   DebugCheckers.cpp
   DereferenceChecker.cpp
   DirectIvarAssignment.cpp
   DivZeroChecker.cpp
   DynamicTypePropagation.cpp
   DynamicTypeChecker.cpp

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

+//===--- CloneChecker.cpp - Clone detection checker -------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+///
+/// \file
+/// CloneChecker is a checker that reports clones in the current translation
+/// unit.
+///
+//===----------------------------------------------------------------------===//
+
+#include "ClangSACheckers.h"
+#include "clang/Analysis/CloneDetection.h"
+#include "clang/Basic/Diagnostic.h"
+#include "clang/StaticAnalyzer/Core/Checker.h"
+#include "clang/StaticAnalyzer/Core/CheckerManager.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
+
+using namespace clang;
+using namespace ento;
+
+namespace {
+class CloneChecker
+    : public Checker<check::ASTCodeBody, check::EndOfTranslationUnit> {
+  mutable CloneDetector CloneDetector;
+
+public:
+  void checkASTCodeBody(const Decl *D, AnalysisManager &Mgr,
+                        BugReporter &BR) const;
+
+  void checkEndOfTranslationUnit(const TranslationUnitDecl *TU,
+                                 AnalysisManager &Mgr, BugReporter &BR) 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.
+  CloneDetector.analyzeCodeBody(D);
+}
+
+void CloneChecker::checkEndOfTranslationUnit(const TranslationUnitDecl *TU,
+                                             AnalysisManager &Mgr,
+                                             BugReporter &BR) const {
+  // At this point, every statement in the translation unit has been analyzed by
+  // the CloneDetector. The only thing left to do is to report the found clones.
+
+  int MinComplexity = Mgr.getAnalyzerOptions().getOptionAsInteger(
+      "MinimumCloneComplexity", 10, this);
+
+  assert(MinComplexity >= 0);
+
+  SourceManager &SM = BR.getSourceManager();
+
+  std::vector<CloneDetector::CloneGroup> CloneGroups;
+  CloneDetector.findClones(CloneGroups, MinComplexity);
+
+  DiagnosticsEngine &DiagEngine = Mgr.getDiagnostic();
+
+  unsigned WarnID = DiagEngine.getCustomDiagID(DiagnosticsEngine::Warning,
+                                               "Detected code clone.");
+
+  unsigned NoteID = DiagEngine.getCustomDiagID(DiagnosticsEngine::Note,
+                                               "Related code clone is here.");
+
+  for (CloneDetector::CloneGroup &Group : CloneGroups) {
+    // For readability reasons we sort the clones by line numbers.
+    std::sort(Group.Sequences.begin(), Group.Sequences.end(),
+              [&SM](const StmtSequence &LHS, const StmtSequence &RHS) {
+                return SM.isBeforeInTranslationUnit(LHS.getStartLoc(),
+                                                    RHS.getStartLoc()) &&
+                       SM.isBeforeInTranslationUnit(LHS.getEndLoc(),
+                                                    RHS.getEndLoc());
+              });
+
+    // We group the clones by printing the first as a warning and all others
+    // as a note.
+    DiagEngine.Report(Group.Sequences.front().getStartLoc(), WarnID);
+    for (unsigned i = 1; i < Group.Sequences.size(); ++i) {
+      DiagEngine.Report(Group.Sequences[i].getStartLoc(), NoteID);
+    }
+  }
+}
+
+//===----------------------------------------------------------------------===//
+// Register CloneChecker
+//===----------------------------------------------------------------------===//
+
+void ento::registerCloneChecker(CheckerManager &Mgr) {
+  Mgr.registerChecker<CloneChecker>();
+}

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

+// RUN: %clang_cc1 -analyze -fblocks -std=c++11 -analyzer-checker=alpha.clone.CloneChecker -verify %s
+
+// This tests if we search for clones in blocks.
+
+void log();
+
+auto BlockA = ^(int a, int b){ // expected-warning{{Detected code clone.}}
+  log();
+  if (a > b)
+    return a;
+  return b;
+};
+
+auto BlockB = ^(int a, int b){ // expected-note{{Related code clone is here.}}
+  log();
+  if (a > b)
+    return a;
+  return b;
+};

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

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

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

+// RUN: %clang_cc1 -analyze -std=c++11 -analyzer-checker=alpha.clone.CloneChecker -verify %s
+
+// This tests if we search for clones in functions.
+
+void log();
+
+int max(int a, int b) { // expected-warning{{Detected code clone.}}
+  log();
+  if (a > b)
+    return a;
+  return b;
+}
+
+int maxClone(int x, int y) { // expected-note{{Related code clone is here.}}
+  log();
+  if (x > y)
+    return x;
+  return y;
+}
+
+// Functions below are not clones and should not be reported.
+
+int foo(int a, int b) { // no-warning
+  return a + b;
+}

cfe/trunk/test/Analysis/copypaste/objc-methods.m

+// RUN: %clang_cc1 -analyze -Wno-objc-root-class -analyzer-checker=alpha.clone.CloneChecker -verify %s
+
+// This tests if we search for clones in Objective-C methods.
+
+@interface A
+- (int) setOk : (int) a : (int) b;
+@end
+
+@implementation A
+- (int) setOk : (int) a : (int) b {  // expected-warning{{Detected code clone.}}
+  if (a > b)
+    return a;
+  return b;
+}
+@end
+
+@interface B
+- (int) setOk : (int) a : (int) b;
+@end
+
+@implementation B
+- (int) setOk : (int) a : (int) b { // expected-note{{Related code clone is here.}}
+  if (a > b)
+    return a;
+  return b;
+}
+@end

cfe/trunk/test/Analysis/copypaste/sub-sequences.cpp

+// RUN: %clang_cc1 -analyze -std=c++11 -analyzer-checker=alpha.clone.CloneChecker -verify %s
+
+// This tests if sub-sequences can match with normal sequences.
+
+void log2(int a);
+void log();
+
+int max(int a, int b) {
+  log2(a);
+  log(); // expected-warning{{Detected code clone.}}
+  if (a > b)
+    return a;
+  return b;
+}
+
+int maxClone(int a, int b) {
+  log(); // expected-note{{Related code clone is here.}}
+  if (a > b)
+    return a;
+  return b;
+}
+
+// Functions below are not clones and should not be reported.
+
+int foo(int a, int b) { // no-warning
+  return a + b;
+}