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

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

149

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

154

Can you move this on the previous line?

167

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

216

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

23

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

46

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

55

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

57

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.

65

Same as above.

85

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

113

Doxygen style /// ?

140

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

162

Indent.

165

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

294

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

21

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

132

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

146

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.

162

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

167

serves -> serve

187

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

202

database -> map?

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

210

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

218

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

include/clang/StaticAnalyzer/Checkers/Checkers.td

668

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

lib/AST/CMakeLists.txt

10

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

57

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

104

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

46

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

53

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

89

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]

176

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.

195

Simplifies to:

StmtSequence ChildSequence(Child, Context);

239

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.

263

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

41

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.

44

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.

46

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

40

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

132

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

lib/AST/CMakeLists.txt

10

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

104

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

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.

include/clang/AST/CloneDetection.h

+//===--- CloneDetection.h - Analyses the structure of 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 <map>
+#include <vector>
+
+namespace clang {
+
+class Stmt;
+class ASTContext;
+class CompoundStmt;
+class TranslationUnitDecl;
+
+/// \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.
+  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(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(Stmt *Stmt, ASTContext *Context);
+
+  /// \brief Constructs an empty StmtSequence.
+  StmtSequence() : StmtSequence(nullptr, nullptr) {}
+
+  /// Returns an iterator-style pointer to the first statement in this sequence.
+  Stmt *const *begin() const;
+
+  /// Returns an iterator-style pointer that points behind the last statement
+  /// in this sequence.
+  Stmt *const *end() const;
+
+  /// Returns the first statement in this sequence.
+  /// This method should only be called on a non-empty StmtSequence object.
+  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.
+  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;
+
+  /// Provides an strict weak ordering operator.
+  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.
+  ///
+  /// 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 clones in source code.
+///
+/// This class first needs to be provided with (possibly multiple) translation
+/// units by passing them \p AnalyzeTranslationUnitDecl .
+/// Afterwards all provided translation units can be searched for 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.
+///
+/// CloneDetector generates search data for efficiently finding clones
+/// in the given statements.
+/// This is done by hashing all statements using a locality-sensitive hash
+/// function that generates identical hash values for similar statement
+/// trees.
+class CloneDetector {
+public:
+  /// Holds the generated data for a StmtSequence
+  struct StmtData {
+    /// The generated hash value.
+    unsigned Hash;
+    /// \brief The complexity of the StmtSequence.
+    ///
+    /// This scalar values 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;
+    StmtData() : Hash(0), Complexity(0) {}
+
+    StmtData(unsigned Hash, unsigned Complexity)
+        : Hash(Hash), Complexity(Complexity) {}
+  };
+
+  /// \brief Generates and stores search data for all statements in the
+  /// given translation unit declarations.
+  ///
+  /// This method can be called multiple times on the same CloneDetector
+  /// to search clones across translation unit boundaries.
+  void AnalyzeTranslationUnitDecl(TranslationUnitDecl *TU);
+
+  /// \brief Returns the generated search data for the given StmtSequence.
+  ///
+  /// \param S the given StmtSequence
+  /// \param Error output parameter that is set to true if no
+  ///        data was generated for the given StmtSequence.
+  ///        This can happen if the given StmtSequence is not part of a
+  ///        translation unit that was passed to \p AnalyzeTranslationUnitDecl
+  ///        so far.
+  StmtData findHash(const StmtSequence &S, bool &Error) {
+    auto I = HashedStmts.find(S);
+    if (I == HashedStmts.end()) {
+      Error = true;
+      return StmtData();
+    }
+    Error = false;
+    return I->second;
+  }
+
+  /// \brief Stores the StmtSequence with its associated data in the search
+  ///        database of this CloneDetector.
+  ///
+  /// StmtSequence objects added by this method are included in the clone
+  /// search.
+  void add(const StmtSequence &S, const StmtData &Data);
+
+  typedef std::vector<StmtSequence> CloneGroup;
+
+  /// \brief Searches all translation units in this CloneDetector for clones.
+  ///
+  /// \param MinGroupComplexity Only return clones which have at least this
+  ///                           complexity value.
+  /// \return a list of found clone groups. Each group contains multiple
+  ///         StmtSequences that were identified to be clones of each other.
+  std::vector<CloneGroup> findClones(unsigned MinGroupComplexity = 10);
+
+private:
+  // Maps each StmtSequence to the search data that was generated for it.
+  std::map<StmtSequence, StmtData> HashedStmts;
+};
+
+} // end namespace clang
+
+#endif // LLVM_CLANG_AST_CLONEDETECTION_H

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 CloneDetection : Package<"clone">;
+
 //===----------------------------------------------------------------------===//
 // Core Checkers.
 //===----------------------------------------------------------------------===//
 
 let ParentPackage = Core in {
 
 def DereferenceChecker : Checker<"NullDereference">,
   HelpText<"Check for dereferences of null pointers">,

   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 = CloneDetection in {
+
+def CloneChecker : Checker<"CloneChecker">,
+  HelpText<"Reports similar pieces of code.">,
+  DescFile<"CloneChecker.cpp">;
+
+} // end "clone"
+

lib/AST/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS support)
 
 add_clang_library(clangAST
   APValue.cpp
   ASTConsumer.cpp
   ASTContext.cpp
   ASTDiagnostic.cpp
   ASTDumper.cpp
   ASTImporter.cpp
   ASTTypeTraits.cpp
   AttrImpl.cpp
+  CloneDetection.cpp
   CXXInheritance.cpp
   Comment.cpp
   CommentBriefParser.cpp
   CommentCommandTraits.cpp
   CommentLexer.cpp
   CommentParser.cpp
   CommentSema.cpp
   Decl.cpp

lib/AST/CloneDetection.cpp

+//===--- CloneDetection.cpp - Analyses the structure of 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/AST/CloneDetection.h"
+
+#include "clang/AST/ASTContext.h"
+#include "clang/AST/RecursiveASTVisitor.h"
+#include "clang/AST/Stmt.h"
+
+using namespace clang;
+
+StmtSequence::StmtSequence(CompoundStmt *Stmt, ASTContext *Context,
+                           unsigned StartIndex, unsigned EndIndex)
+    : S(Stmt), Context(Context), StartIndex(StartIndex), EndIndex(EndIndex) {
+  assert(Stmt && Context && "Both Stmt and Context need to be valid pointers");
+  assert(StartIndex < EndIndex && "Given array should not be empty");
+  assert(EndIndex <= Stmt->size() && "Given array too big for this Stmt");
+}
+
+StmtSequence::StmtSequence(Stmt *Stmt, ASTContext *Context)
+    : S(Stmt), Context(Context), StartIndex(0), EndIndex(0) {
+  // Test against passing StmtSequence(nullptr, valid_ptr) or
+  // StmtSequence(valid_ptr, nullptr).
+  assert((!Stmt && !Context) || (Stmt && Context));
+}
+
+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;
+
+  // Otherwise check if the start and end locations of the current sequence
+  // surround the other sequence.
+  bool StartIsInBounds = Context->getSourceManager().isBeforeInTranslationUnit(
+                             getStartLoc(), Other.getStartLoc()) ||
+                         getStartLoc() == Other.getStartLoc();
+  bool EndIsInBounds = Context->getSourceManager().isBeforeInTranslationUnit(
+                           Other.getEndLoc(), getEndLoc()) ||
+                       Other.getEndLoc() == getEndLoc();
+  return StartIsInBounds && EndIsInBounds;
+}
+
+Stmt *const *StmtSequence::begin() const {
+  if (holdsSequence()) {
+    auto CS = static_cast<CompoundStmt *>(S);
+    return CS->body_begin() + StartIndex;
+  }
+  return &S;
+}
+
+Stmt *const *StmtSequence::end() const {
+  if (holdsSequence()) {
+    auto CS = static_cast<CompoundStmt *>(S);
+    return CS->body_begin() + EndIndex;
+  }
+  return &S;
+}
+
+SourceLocation StmtSequence::getStartLoc() const {
+  return front()->getLocStart();
+}
+
+SourceLocation StmtSequence::getEndLoc() const { return back()->getLocEnd(); }
+
+namespace {
+/// Utility class for computing a hash value.
+class HashValue {
+  unsigned Value = 0;
+
+public:
+  /// Computes the given data into the hash value.
+  void addData(unsigned Data) {
+    Value *= 53;
+    Value += Data;
+  }
+
+  /// Returns the hash value.
+  unsigned getValue() { return Value; }
+};
+} // end anonymous namespace
+
+namespace {
+/// Traverses the AST and calculates hash values and complexity values
+/// for all statements. The results are stored in a CloneDetector
+/// object.
+///
+/// This calculation happens in linear time and each statement is only
+/// visited a fixed amount of times during this process.
+/// The hash value for a statement is first calculated from the data stored
+/// directly in the statement object.
+/// Afterwards, the hash values of the children are calculated into the
+/// computed hash value.
+class HashVisitor : public RecursiveASTVisitor<HashVisitor> {
+
+  static const unsigned NullChildHashValue = 313;
+
+public:
+  explicit HashVisitor(CloneDetector &CD, ASTContext &Context)
+      : CD(CD), Context(Context) {}
+
+  // We need to traverse postorder over the AST for our algorithm
+  // to work as each parent expects that its children were already hashed.
+  bool shouldTraversePostOrder() const { return true; }
+
+  bool VisitStmt(Stmt *S);
+
+private:
+  void HandleChildHashes(HashValue &Hash, unsigned &Complexity,
+                         Stmt::child_iterator Iterator, unsigned StartPos,
+                         unsigned Length) {
+    auto StartIterator = Iterator;
+    for (unsigned I = 0; I < StartPos; ++I)
+      ++StartIterator;
+    auto EndIterator = Iterator;
+    for (unsigned I = 0; I < Length; ++I)
+      ++EndIterator;
+    HandleChildHashes(Hash, Complexity, StartIterator, EndIterator);
+  }
+
+  /// Iterates over the specified Stmt array and computes the hash
+  /// values of all statements into the given hash value.
+  /// Also, the complexity of all statements is added to the given
+  /// complexity value.
+  void HandleChildHashes(HashValue &Hash, unsigned &Complexity,
+                         Stmt::child_iterator StartIterator,
+                         Stmt::child_iterator EndIterator) {
+    // Iterate over each child in the sub-sequence.
+    for (auto I = StartIterator; I != EndIterator; ++I) {
+      Stmt *Child = *I;
+      if (Child == nullptr) {
+        ++Complexity;
+        // We use an placeholder hash value for null children.
+        Hash.addData(NullChildHashValue);
+      } else {
+        StmtSequence ChildSequence(StmtSequence(Child, &Context));
+
+        bool Error;
+        CloneDetector::StmtData Data = CD.findHash(ChildSequence, Error);
+        assert(!Error && "Child statement wasn't hashed before parent.");
+
+        Complexity += Data.Complexity;
+        Hash.addData(Data.Hash);
+      }
+    }
+  }
+
+  // Saves the current hash value into the persistent storage of this
+  // CloneDetector.
+  void SaveData(StmtSequence CurrentStmt, HashValue Hash,
+                       unsigned Complexity);
+
+  CloneDetector &CD;
+  ASTContext &Context;
+};
+} // end anonymous namespace
+
+bool HashVisitor::VisitStmt(Stmt *S) {
+  StmtSequence CurrentStmt(S, &Context);
+  HashValue Hash;
+  unsigned Complexity = 1;
+
+  // The only relevant data for now is the class of the statement,
+  // so we calculate the hash class into the current hash value.
+  // TODO: Handle statement class specific data.
+  Hash.addData(S->getStmtClass());
+
+  // Incorporate the hash values of all child Stmts into the current
+  // hash value.
+  HandleChildHashes(Hash, Complexity, S->child_begin(), S->child_end());
+
+  SaveData(CurrentStmt, Hash, Complexity);
+  return true;
+}
+
+void HashVisitor::SaveData(StmtSequence CurrentStmt, HashValue Hash,
+                                  unsigned Complexity) {
+  // Save current dat to the CloneDetector.
+  CloneDetector::StmtData Data(Hash.getValue(), Complexity);
+  CD.add(CurrentStmt, Data);
+
+  // If the currently hashed statement is a CompoundStmt, we also
+  // need to calculate the hash values for all possible sub-sequences
+  // in the body of the CompoundStmt.
+  auto CS = dyn_cast<CompoundStmt>(CurrentStmt.front());
+  if (!CS)
+    return;
+
+  // The length of the sub-sequence. We don't need to hash sequences
+  // with the length 1 as they are already handled when we hashed the
+  // children.
+  // We also don't need to hash the sub-sequence that contains the
+  // whole body as this would be equal to the hash of the CompoundStmt itself.
+  for (unsigned Length = 2; Length < CS->size(); ++Length) {
+    // The start index in the body of the CompoundStmt.
+    // We increase the position and rehash until the end of the sub-sequence
+    // reaches the end of the CompoundStmt body.
+    for (unsigned Pos = 0; Pos <= CS->size() - Length; ++Pos) {
+      HashValue SubHash;
+      unsigned SubComplexity = 1;
+      StmtSequence Sequence(CS, &Context, Pos, Pos + Length);
+
+      // We consider a sub-sequence to be CompoundStmt that only contains
+      // the children in the sub-sequence. This is necessary for matching
+      // sub-sequences with full CompoundStmts.
+      SubHash.addData(CS->getStmtClass());
+
+      HandleChildHashes(SubHash, SubComplexity, CS->child_begin(), Pos, Length);
+
+      CloneDetector::StmtData SubData(SubHash.getValue(), SubComplexity);
+      CD.add(Sequence, SubData);
+    }
+  }
+}
+
+void CloneDetector::AnalyzeTranslationUnitDecl(TranslationUnitDecl *TU) {
+  HashVisitor visitor(*this, TU->getASTContext());
+  visitor.TraverseDecl(TU);
+}
+
+void CloneDetector::add(const StmtSequence &S, const StmtData &Data) {
+  assert(!S.empty());
+  HashedStmts[S] = Data;
+}
+
+namespace {
+/// Returns true if and only if \p Stmt contains at least one
+/// other sequence in the \p Group.
+bool StmtContainsAnyInGroup(StmtSequence &Stmt,
+                            CloneDetector::CloneGroup &Group) {
+  for (StmtSequence &GroupStmt : Group) {
+    if (Stmt.contains(GroupStmt))
+      return true;
+  }
+  return false;
+}
+
+/// Returns true if and only if all sequences in \p OtherGroup are contained
+/// by a sequence in \p Group.
+bool GroupContains(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;
+
+  for (StmtSequence &Stmt : Group) {
+    if (!StmtContainsAnyInGroup(Stmt, OtherGroup))
+      return false;
+  }
+  return true;
+}
+} // end anonymous namespace
+
+std::vector<CloneDetector::CloneGroup>
+CloneDetector::findClones(unsigned MinGroupComplexity) {
+  std::vector<CloneGroup> Result;
+
+  std::map<unsigned, CloneGroup> GroupsByHash;
+
+  // Create a CloneGroup for every known statement.
+  for (auto &Pair : HashedStmts) {
+    // but ignore statements that don't fulfill the complexity requirement.
+    if (Pair.second.Complexity > MinGroupComplexity) {
+      GroupsByHash[Pair.second.Hash].push_back(Pair.first);
+    }
+  }
+
+  // Put all groups that now contain at least one sequence into the
+  // result. We still need to filter the Result.
+  for (auto &HashGroupPair : GroupsByHash) {
+    if (HashGroupPair.second.size() > 1) {
+      Result.push_back(HashGroupPair.second);
+    }
+  }
+
+  std::set<unsigned> IndexesToRemove;
+
+  // Compare every group in the result with the others. If one groups
+  // contains another group, we only need to return the bigger group.
+  for (unsigned I = 0; I < Result.size(); ++I) {
+    for (unsigned J = 0; J < Result.size(); ++J) {
+      if (I != J) {
+        if (GroupContains(Result[J], Result[I])) {
+          IndexesToRemove.insert(I);
+          break;
+        }
+      }
+    }
+  }
+
+  for (auto Iter = IndexesToRemove.rbegin(); Iter != IndexesToRemove.rend();
+       ++Iter) {
+    Result.erase(Result.begin() + (*Iter));
+  }
+
+  return Result;
+}

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
   DeadStoresChecker.cpp
   DebugCheckers.cpp
   DereferenceChecker.cpp
   DirectIvarAssignment.cpp
   DivZeroChecker.cpp
   DynamicTypePropagation.cpp
   DynamicTypeChecker.cpp
   ExprInspectionChecker.cpp

lib/StaticAnalyzer/Checkers/CloneChecker.cpp

+//===--- CloneDetection.cpp - Clone detection checkers ----------*- 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/AST/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::EndOfTranslationUnit> {
+
+public:
+  void checkEndOfTranslationUnit(const TranslationUnitDecl *TU,
+                                 AnalysisManager &Mgr, BugReporter &BR) const;
+};
+} // end anonymous namespace
+
+void CloneChecker::checkEndOfTranslationUnit(const TranslationUnitDecl *TU,
+                                             AnalysisManager &Mgr,
+                                             BugReporter &BR) const {
+  CloneDetector CloneDetector;
+  CloneDetector.AnalyzeTranslationUnitDecl(
+      TU->getASTContext().getTranslationUnitDecl());
+
+  std::vector<CloneDetector::CloneGroup> CloneGroups =
+      CloneDetector.findClones();
+
+  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) {
+    DiagEngine.Report(Group.front().getStartLoc(), WarnID);
+    for (unsigned J = 1; J < Group.size(); ++J) {
+      DiagEngine.Report(Group[J].getStartLoc(), NoteID);
+    }
+  }
+}
+
+//===----------------------------------------------------------------------===//
+// Register CloneChecker
+//===----------------------------------------------------------------------===//
+
+void ento::registerCloneChecker(CheckerManager &Mgr) {
+  Mgr.registerChecker<CloneChecker>();
+}

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

+// RUN: %clang_cc1 -analyze -std=c++11 -analyzer-checker=clone.CloneChecker -verify %s
+
+void log();
+
+int max(int a, int b) { // expected-warning{{Detected code clone.}}
+  log();
+  if (a > b)
+    return a;
+  return b;
+}
+
+int maxClone(int a, int b) { // expected-note{{Related code clone is here.}}
+  log();
+  if (a > b)
+    return a;
+  return b;
+}
+
+// False positives below. These clones should not be reported.
+
+// 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;
+}
+
+// Functions below are not clones and should not be reported.
+
+int foo(int a, int b) {
+  return a + b;
+}

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

+// RUN: %clang_cc1 -analyze -std=c++11 -analyzer-checker=clone.CloneChecker -verify %s
+
+// We test if sub-sequences can match with normal sequences containing only
+// a single statement.
+
+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) {
+  return a + b;
+}