[analyzer] Make StmtDataCollector customizable

[johannes]

Summary

This moves the data collection macro calls for Stmt nodes
to lib/AST/StmtDataCollectors.inc

Users can subclass ConstStmtVisitor and include StmtDataCollectors.inc
to define visitor methods for each Stmt subclass. This makes it also
possible to customize the visit methods as exemplified in
CloneDetection.cpp.

Move helper methods for data collection to a new module,
AST/DataCollection.

Add data collection for DeclRefExpr, MemberExpr and some literals, tested
in unittests/AST/DataCollectionTest.cpp.

[teemperor]

Very well done, I really like this patch! I added a few remarks mostly about the comments that need some small adjusting.

I'm wondering what would be a nice way of creating a StmtDataCollector that is faster but only works for single translation units (e.g. it only hashes the pointer values of decls instead of their qualified name)? The use case here would be Stmt::Profile and the CloneDetector which could be set to a single-TU-mode in the CloneChecker. For Stmt::Profile it would ensure we don't degrade performance from the current version, for the CloneChecker we probably get a reasonable performance boost (as the hashing is currently the last remaining bottle neck).

@arphaman Any suggestions who could review/approve the additions to AST/?

include/clang/AST/DataCollection.h

19 ↗

(On Diff #110920)

I think we need another namespace here because I don't like a generic function name like addDataToConsumer in the clang namespace. Maybe clang::data_collection::addDataToConsumer or something like that.

lib/AST/StmtDataCollectors.inc

5 ↗

(On Diff #110920)

I know this is from my code, but as you're anyway touching this line, could you fix this comment? It should be "that non-macro-generated code` instead of that macro generated. Thanks!

lib/Analysis/CloneDetection.cpp

172 ↗

(On Diff #110920)

I think this line can be removed now.

174 ↗

(On Diff #110920)

what a code clone is -> what a type II code clone is

210 ↗

(On Diff #110920)

Should be Type II clones ignore variable names and literals, so let's skip them

[arphaman]

In D36664#841758, @teemperor wrote:

Very well done, I really like this patch! I added a few remarks mostly about the comments that need some small adjusting.

I'm wondering what would be a nice way of creating a StmtDataCollector that is faster but only works for single translation units (e.g. it only hashes the pointer values of decls instead of their qualified name)? The use case here would be Stmt::Profile and the CloneDetector which could be set to a single-TU-mode in the CloneChecker. For Stmt::Profile it would ensure we don't degrade performance from the current version, for the CloneChecker we probably get a reasonable performance boost (as the hashing is currently the last remaining bottle neck).

@arphaman Any suggestions who could review/approve the additions to AST/?

I guess @rsmith, but he's usually busy. I don't think this patch requires some special approval though.

This patch adds support for things like literals and DeclRefExpr and MemberExpr, but they're untested. They should either be added in a follow-up patch or tested with an appropriate unittest in unittests/AST or unittests/Tooling.

[johannes]

• fix comments
• add unittest for the new node kinds
• make addData() take a const reference

[johannes]

add

[johannes]

In D36664#841758, @teemperor wrote:

Very well done, I really like this patch! I added a few remarks mostly about the comments that need some small adjusting.

I'm wondering what would be a nice way of creating a StmtDataCollector that is faster but only works for single translation units (e.g. it only hashes the pointer values of decls instead of their qualified name)? The use case here would be Stmt::Profile and the CloneDetector which could be set to a single-TU-mode in the CloneChecker. For Stmt::Profile it would ensure we don't degrade performance from the current version, for the CloneChecker we probably get a reasonable performance boost (as the hashing is currently the last remaining bottle neck).

@arphaman Any suggestions who could review/approve the additions to AST/?

So we want at least two different modes

• unstable / hash pointer members
• stable / follow pointer members

We can do this by using two macros with different names. So we can split DEF_ADD_DATA in something like COLLECT_DATA_STABLE and COLLECT_DATA_UNSTABLE
Both would share the collection of POD members, so it makes sense to use a third macro for this.

So the code in StmtDataCollectors.inc assumes that DataCollection.h has been included, and that there is a addData() function as well as an ASTContext &Context in the current scope.
These things should be documented in DataCollection.h I guess.

Since StmtDataCollectors.inc resides in lib I have to use relative paths (so the include directive looks different depending on the current file), we have to live with this, right?

[teemperor]

Sorry for the delay, was on vacation.

Since StmtDataCollectors.inc resides in lib I have to use relative paths (so the include directive looks different depending on the current file), we have to live with this, right?

That's right, but do we want this to be in lib/ ? There users can't access this code to build their own DataCollector (at least when they build against an installed clang version where this inc file doesn't get installed). And if someone uses this file from a clang header by accident we get errors about this missing file with installed clang versions (and I think the build bots don't perform install tests, so it probably breaks silently).

We probably also can't just move it into include/ because *.inc files there break some CMake sanity checks IIRC, so I think the best way forward is to tablegen this file which also makes the StmtDataCollectors.inc file more readable.

These things should be documented in DataCollection.h I guess.

Agreed, could you do that?

I think this can go in with just these documentation changes (especially since its GSoC related and we're in the last week), so please add them and then LGTM. Stable hashes and tablegen can be a follow-up patches.

cfe/trunk/include/clang/AST/DataCollection.h

+//===--- DatatCollection.h --------------------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+/// \file
+/// \brief This file declares helper methods for collecting data from AST nodes.
+///
+/// To collect data from Stmt nodes, subclass ConstStmtVisitor and include
+/// StmtDataCollectors.inc after defining the macros that you need. This
+/// provides data collection implementations for most Stmt kinds. Note
+/// that that code requires some conditions to be met:
+///
+///   - There must be a method addData(const T &Data) that accepts strings,
+///     integral types as well as QualType. All data is forwarded using
+///     to this method.
+///   - The ASTContext of the Stmt must be accessible by the name Context.
+///
+/// It is also possible to override individual visit methods. Have a look at
+/// the DataCollector in lib/Analysis/CloneDetection.cpp for a usage example.
+///
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_AST_DATACOLLECTION_H
+#define LLVM_CLANG_AST_DATACOLLECTION_H
+
+#include "clang/AST/ASTContext.h"
+
+namespace clang {
+namespace data_collection {
+
+/// 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.
+std::string getMacroStack(SourceLocation Loc, ASTContext &Context);
+
+/// Utility functions for implementing addData() for a consumer that has a
+/// method update(StringRef)
+template <class T>
+void addDataToConsumer(T &DataConsumer, llvm::StringRef Str) {
+  DataConsumer.update(Str);
+}
+
+template <class T> void addDataToConsumer(T &DataConsumer, const QualType &QT) {
+  addDataToConsumer(DataConsumer, QT.getAsString());
+}
+
+template <class T, class Type>
+typename std::enable_if<
+    std::is_integral<Type>::value || std::is_enum<Type>::value ||
+    std::is_convertible<Type, size_t>::value // for llvm::hash_code
+    >::type
+addDataToConsumer(T &DataConsumer, Type Data) {
+  DataConsumer.update(StringRef(reinterpret_cast<char *>(&Data), sizeof(Data)));
+}
+
+} // end namespace data_collection
+} // end namespace clang
+
+#endif // LLVM_CLANG_AST_DATACOLLECTION_H

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

 /// \file
 /// This file defines classes for searching and analyzing source code clones.
 ///
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_AST_CLONEDETECTION_H
 #define LLVM_CLANG_AST_CLONEDETECTION_H
 
-#include "clang/AST/DeclTemplate.h"
 #include "clang/AST/StmtVisitor.h"
-#include "clang/Basic/SourceLocation.h"
-#include "llvm/ADT/SmallVector.h"
-#include "llvm/ADT/StringRef.h"
 #include "llvm/Support/Regex.h"
 #include <vector>
 
 namespace clang {
 
 class Stmt;
 class Decl;
 class VarDecl;
 class ASTContext;
 class CompoundStmt;
 
-namespace clone_detection {
-
-/// 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.
-std::string getMacroStack(SourceLocation Loc, ASTContext &Context);
-
-/// 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;
-  /// The data sink to which all data is forwarded.
-  T &DataConsumer;
-
-public:
-  /// 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);
-  }
-
-  typedef unsigned DataPiece;
-
-  // Below are utility methods for appending different data to the vector.
-
-  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()); }
-
-// The functions below collect the class specific data of each Stmt subclass.
-
-// Utility macro for defining a visit method for a given class. This method
-// calls back to the ConstStmtVisitor to visit all parent classes.
-#define DEF_ADD_DATA(CLASS, CODE)                                              \
-  void Visit##CLASS(const CLASS *S) {                                          \
-    CODE;                                                                      \
-    ConstStmtVisitor<StmtDataCollector>::Visit##CLASS(S);                      \
-  }
-
-  DEF_ADD_DATA(Stmt, {
-    addData(S->getStmtClass());
-    // This ensures that macro generated code isn't identical to macro-generated
-    // code.
-    addData(getMacroStack(S->getLocStart(), Context));
-    addData(getMacroStack(S->getLocEnd(), Context));
-  })
-  DEF_ADD_DATA(Expr, { addData(S->getType()); })
-
-  //--- Builtin functionality ----------------------------------------------//
-  DEF_ADD_DATA(ArrayTypeTraitExpr, { addData(S->getTrait()); })
-  DEF_ADD_DATA(ExpressionTraitExpr, { addData(S->getTrait()); })
-  DEF_ADD_DATA(PredefinedExpr, { addData(S->getIdentType()); })
-  DEF_ADD_DATA(TypeTraitExpr, {
-    addData(S->getTrait());
-    for (unsigned i = 0; i < S->getNumArgs(); ++i)
-      addData(S->getArg(i)->getType());
-  })
-
-  //--- Calls --------------------------------------------------------------//
-  DEF_ADD_DATA(CallExpr, {
-    // Function pointers don't have a callee and we just skip hashing it.
-    if (const FunctionDecl *D = S->getDirectCallee()) {
-      // If the function is a template specialization, we also need to handle
-      // the template arguments as they are not included in the qualified name.
-      if (auto Args = D->getTemplateSpecializationArgs()) {
-        std::string ArgString;
-
-        // Print all template arguments into ArgString
-        llvm::raw_string_ostream OS(ArgString);
-        for (unsigned i = 0; i < Args->size(); ++i) {
-          Args->get(i).print(Context.getLangOpts(), OS);
-          // Add a padding character so that 'foo<X, XX>()' != 'foo<XX, X>()'.
-          OS << '\n';
-        }
-        OS.flush();
-
-        addData(ArgString);
-      }
-      addData(D->getQualifiedNameAsString());
-    }
-  })
-
-  //--- Exceptions ---------------------------------------------------------//
-  DEF_ADD_DATA(CXXCatchStmt, { addData(S->getCaughtType()); })
-
-  //--- C++ OOP Stmts ------------------------------------------------------//
-  DEF_ADD_DATA(CXXDeleteExpr, {
-    addData(S->isArrayFormAsWritten());
-    addData(S->isGlobalDelete());
-  })
-
-  //--- Casts --------------------------------------------------------------//
-  DEF_ADD_DATA(ObjCBridgedCastExpr, { addData(S->getBridgeKind()); })
-
-  //--- Miscellaneous Exprs ------------------------------------------------//
-  DEF_ADD_DATA(BinaryOperator, { addData(S->getOpcode()); })
-  DEF_ADD_DATA(UnaryOperator, { addData(S->getOpcode()); })
-
-  //--- Control flow -------------------------------------------------------//
-  DEF_ADD_DATA(GotoStmt, { addData(S->getLabel()->getName()); })
-  DEF_ADD_DATA(IndirectGotoStmt, {
-    if (S->getConstantTarget())
-      addData(S->getConstantTarget()->getName());
-  })
-  DEF_ADD_DATA(LabelStmt, { addData(S->getDecl()->getName()); })
-  DEF_ADD_DATA(MSDependentExistsStmt, { addData(S->isIfExists()); })
-  DEF_ADD_DATA(AddrLabelExpr, { addData(S->getLabel()->getName()); })
-
-  //--- Objective-C --------------------------------------------------------//
-  DEF_ADD_DATA(ObjCIndirectCopyRestoreExpr, { addData(S->shouldCopy()); })
-  DEF_ADD_DATA(ObjCPropertyRefExpr, {
-    addData(S->isSuperReceiver());
-    addData(S->isImplicitProperty());
-  })
-  DEF_ADD_DATA(ObjCAtCatchStmt, { addData(S->hasEllipsis()); })
-
-  //--- Miscellaneous Stmts ------------------------------------------------//
-  DEF_ADD_DATA(CXXFoldExpr, {
-    addData(S->isRightFold());
-    addData(S->getOperator());
-  })
-  DEF_ADD_DATA(GenericSelectionExpr, {
-    for (unsigned i = 0; i < S->getNumAssocs(); ++i) {
-      addData(S->getAssocType(i));
-    }
-  })
-  DEF_ADD_DATA(LambdaExpr, {
-    for (const LambdaCapture &C : S->captures()) {
-      addData(C.isPackExpansion());
-      addData(C.getCaptureKind());
-      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<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());
-    addData(S->isVolatile());
-    addData(S->generateAsmString(Context));
-    for (unsigned i = 0; i < S->getNumInputs(); ++i) {
-      addData(S->getInputConstraint(i));
-    }
-    for (unsigned i = 0; i < S->getNumOutputs(); ++i) {
-      addData(S->getOutputConstraint(i));
-    }
-    for (unsigned i = 0; i < S->getNumClobbers(); ++i) {
-      addData(S->getClobber(i));
-    }
-  })
-  DEF_ADD_DATA(AttributedStmt, {
-    for (const Attr *A : S->getAttrs()) {
-      addData(std::string(A->getSpelling()));
-    }
-  })
-};
-} // namespace clone_detection
-
 /// 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.

cfe/trunk/lib/AST/CMakeLists.txt

add_clang_library(clangAST
   AttrImpl.cpp
   CXXInheritance.cpp
   Comment.cpp
   CommentBriefParser.cpp
   CommentCommandTraits.cpp
   CommentLexer.cpp
   CommentParser.cpp
   CommentSema.cpp
+  DataCollection.cpp
   Decl.cpp
   DeclarationName.cpp
   DeclBase.cpp
   DeclCXX.cpp
   DeclFriend.cpp
   DeclGroup.cpp
   DeclObjC.cpp
   DeclOpenMP.cpp

cfe/trunk/lib/AST/DataCollection.cpp

+//===-- DataCollection.cpp --------------------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/AST/DataCollection.h"
+
+#include "clang/Lex/Lexer.h"
+
+namespace clang {
+namespace data_collection {
+
+/// 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 << " ";
+}
+
+/// 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.
+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;
+}
+
+} // end namespace data_collection
+} // end namespace clang

cfe/trunk/lib/AST/StmtDataCollectors.inc

+// The functions below collect the class specific data of each Stmt subclass.
+
+DEF_ADD_DATA(Stmt, {
+  addData(S->getStmtClass());
+  // This ensures that non-macro-generated code isn't identical to
+  // macro-generated code.
+  addData(data_collection::getMacroStack(S->getLocStart(), Context));
+  addData(data_collection::getMacroStack(S->getLocEnd(), Context));
+})
+DEF_ADD_DATA(Expr, { addData(S->getType()); })
+
+//--- Builtin functionality ----------------------------------------------//
+DEF_ADD_DATA(ArrayTypeTraitExpr, { addData(S->getTrait()); })
+DEF_ADD_DATA(ExpressionTraitExpr, { addData(S->getTrait()); })
+DEF_ADD_DATA(PredefinedExpr, { addData(S->getIdentType()); })
+DEF_ADD_DATA(TypeTraitExpr, {
+  addData(S->getTrait());
+  for (unsigned i = 0; i < S->getNumArgs(); ++i)
+    addData(S->getArg(i)->getType());
+})
+
+//--- Calls --------------------------------------------------------------//
+DEF_ADD_DATA(CallExpr, {
+  // Function pointers don't have a callee and we just skip hashing it.
+  if (const FunctionDecl *D = S->getDirectCallee()) {
+    // If the function is a template specialization, we also need to handle
+    // the template arguments as they are not included in the qualified name.
+    if (auto Args = D->getTemplateSpecializationArgs()) {
+      std::string ArgString;
+
+      // Print all template arguments into ArgString
+      llvm::raw_string_ostream OS(ArgString);
+      for (unsigned i = 0; i < Args->size(); ++i) {
+        Args->get(i).print(Context.getLangOpts(), OS);
+        // Add a padding character so that 'foo<X, XX>()' != 'foo<XX, X>()'.
+        OS << '\n';
+      }
+      OS.flush();
+
+      addData(ArgString);
+    }
+    addData(D->getQualifiedNameAsString());
+  }
+})
+
+//--- Value references ---------------------------------------------------//
+DEF_ADD_DATA(DeclRefExpr,
+             { addData(S->getDecl()->getQualifiedNameAsString()); })
+DEF_ADD_DATA(MemberExpr,
+             { addData(S->getMemberDecl()->getName()); })
+
+//--- Literals -----------------------------------------------------------//
+DEF_ADD_DATA(IntegerLiteral, { addData(llvm::hash_value(S->getValue())); })
+DEF_ADD_DATA(FloatingLiteral, { addData(llvm::hash_value(S->getValue())); })
+DEF_ADD_DATA(StringLiteral, { addData(S->getString()); })
+DEF_ADD_DATA(CXXBoolLiteralExpr, { addData(S->getValue()); })
+DEF_ADD_DATA(CharacterLiteral, { addData(S->getValue()); })
+
+//--- Exceptions ---------------------------------------------------------//
+DEF_ADD_DATA(CXXCatchStmt, { addData(S->getCaughtType()); })
+
+//--- C++ OOP Stmts ------------------------------------------------------//
+DEF_ADD_DATA(CXXDeleteExpr, {
+  addData(S->isArrayFormAsWritten());
+  addData(S->isGlobalDelete());
+})
+
+//--- Casts --------------------------------------------------------------//
+DEF_ADD_DATA(ObjCBridgedCastExpr, { addData(S->getBridgeKind()); })
+
+//--- Miscellaneous Exprs ------------------------------------------------//
+DEF_ADD_DATA(BinaryOperator, { addData(S->getOpcode()); })
+DEF_ADD_DATA(UnaryOperator, { addData(S->getOpcode()); })
+
+//--- Control flow -------------------------------------------------------//
+DEF_ADD_DATA(GotoStmt, { addData(S->getLabel()->getName()); })
+DEF_ADD_DATA(IndirectGotoStmt, {
+  if (S->getConstantTarget())
+    addData(S->getConstantTarget()->getName());
+})
+DEF_ADD_DATA(LabelStmt, { addData(S->getDecl()->getName()); })
+DEF_ADD_DATA(MSDependentExistsStmt, { addData(S->isIfExists()); })
+DEF_ADD_DATA(AddrLabelExpr, { addData(S->getLabel()->getName()); })
+
+//--- Objective-C --------------------------------------------------------//
+DEF_ADD_DATA(ObjCIndirectCopyRestoreExpr, { addData(S->shouldCopy()); })
+DEF_ADD_DATA(ObjCPropertyRefExpr, {
+  addData(S->isSuperReceiver());
+  addData(S->isImplicitProperty());
+})
+DEF_ADD_DATA(ObjCAtCatchStmt, { addData(S->hasEllipsis()); })
+
+//--- Miscellaneous Stmts ------------------------------------------------//
+DEF_ADD_DATA(CXXFoldExpr, {
+  addData(S->isRightFold());
+  addData(S->getOperator());
+})
+DEF_ADD_DATA(GenericSelectionExpr, {
+  for (unsigned i = 0; i < S->getNumAssocs(); ++i) {
+    addData(S->getAssocType(i));
+  }
+})
+DEF_ADD_DATA(LambdaExpr, {
+  for (const LambdaCapture &C : S->captures()) {
+    addData(C.isPackExpansion());
+    addData(C.getCaptureKind());
+    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<unsigned>(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());
+  addData(S->isVolatile());
+  addData(S->generateAsmString(Context));
+  for (unsigned i = 0; i < S->getNumInputs(); ++i) {
+    addData(S->getInputConstraint(i));
+  }
+  for (unsigned i = 0; i < S->getNumOutputs(); ++i) {
+    addData(S->getOutputConstraint(i));
+  }
+  for (unsigned i = 0; i < S->getNumClobbers(); ++i) {
+    addData(S->getClobber(i));
+  }
+})
+DEF_ADD_DATA(AttributedStmt, {
+  for (const Attr *A : S->getAttrs()) {
+    addData(std::string(A->getSpelling()));
+  }
+})
+#undef DEF_ADD_DATA

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 "clang/Lex/Lexer.h"
+#include "clang/AST/DataCollection.h"
+#include "clang/AST/DeclTemplate.h"
 #include "llvm/Support/MD5.h"
-#include "llvm/Support/raw_ostream.h"
 #include "llvm/Support/Path.h"
 
 using namespace clang;
-using namespace clang::clone_detection;
 
 StmtSequence::StmtSequence(const CompoundStmt *Stmt, const Decl *D,
                            unsigned StartIndex, unsigned 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");
 }

 }
 
 SourceLocation StmtSequence::getEndLoc() const { return back()->getLocEnd(); }
 
 SourceRange StmtSequence::getSourceRange() const {
   return SourceRange(getStartLoc(), getEndLoc());
 }
 
-/// 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 << " ";
-}
-
-std::string clone_detection::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;
-}
-
 void CloneDetector::analyzeCodeBody(const Decl *D) {
   assert(D);
   assert(D->hasBody());
 
   Sequences.push_back(StmtSequence(D->getBody(), D));
 }
 
 /// Returns true if and only if \p Stmt contains at least one other
void OnlyLargestCloneConstraint::constrain(
   // 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);
   }
 }
 
-bool FilenamePatternConstraint::isAutoGenerated(const CloneDetector::CloneGroup &Group) {
+bool FilenamePatternConstraint::isAutoGenerated(
+    const CloneDetector::CloneGroup &Group) {
   std::string Error;
-  if (IgnoredFilesPattern.empty() || Group.empty() || 
+  if (IgnoredFilesPattern.empty() || Group.empty() ||
       !IgnoredFilesRegex->isValid(Error))
     return false;
 
   for (const StmtSequence &S : Group) {
     const SourceManager &SM = S.getASTContext().getSourceManager();
-    StringRef Filename = llvm::sys::path::filename(SM.getFilename(
-        S.getContainingDecl()->getLocation()));
+    StringRef Filename = llvm::sys::path::filename(
+        SM.getFilename(S.getContainingDecl()->getLocation()));
     if (IgnoredFilesRegex->match(Filename))
       return true;
   }
 
   return false;
 }
 
+/// This class defines what a type II 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)
+namespace {
+template <class T>
+class CloneTypeIIStmtDataCollector
+    : public ConstStmtVisitor<CloneTypeIIStmtDataCollector<T>> {
+  ASTContext &Context;
+  /// The data sink to which all data is forwarded.
+  T &DataConsumer;
+
+  template <class Ty> void addData(const Ty &Data) {
+    data_collection::addDataToConsumer(DataConsumer, Data);
+  }
+
+public:
+  CloneTypeIIStmtDataCollector(const Stmt *S, ASTContext &Context,
+                               T &DataConsumer)
+      : Context(Context), DataConsumer(DataConsumer) {
+    this->Visit(S);
+  }
+
+// Define a visit method for each class to collect data and subsequently visit
+// all parent classes. This uses a template so that custom visit methods by us
+// take precedence.
+#define DEF_ADD_DATA(CLASS, CODE)                                              \
+  template <class = void> void Visit##CLASS(const CLASS *S) {                  \
+    CODE;                                                                      \
+    ConstStmtVisitor<CloneTypeIIStmtDataCollector<T>>::Visit##CLASS(S);        \
+  }
+
+#include "../AST/StmtDataCollectors.inc"
+
+// Type II clones ignore variable names and literals, so let's skip them.
+#define SKIP(CLASS)                                                            \
+  void Visit##CLASS(const CLASS *S) {                                          \
+    ConstStmtVisitor<CloneTypeIIStmtDataCollector<T>>::Visit##CLASS(S);        \
+  }
+  SKIP(DeclRefExpr)
+  SKIP(MemberExpr)
+  SKIP(IntegerLiteral)
+  SKIP(FloatingLiteral)
+  SKIP(StringLiteral)
+  SKIP(CXXBoolLiteralExpr)
+  SKIP(CharacterLiteral)
+#undef SKIP
+};
+} // end anonymous namespace
+
 static size_t createHash(llvm::MD5 &Hash) {
   size_t HashCode;
 
   // Create the final hash code for the current Stmt.
   llvm::MD5::MD5Result HashResult;
   Hash.final(HashResult);
 
   // 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)));
 
   return HashCode;
 }
 
 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();
 
-  StmtDataCollector<llvm::MD5>(S, Context, Hash);
+  CloneTypeIIStmtDataCollector<llvm::MD5>(S, Context, Hash);
 
   auto CS = dyn_cast<CompoundStmt>(S);
   SmallVector<size_t, 8> ChildHashes;
 
   for (const Stmt *Child : S->children()) {
     if (Child == nullptr) {
       ChildHashes.push_back(0);
       continue;

 };
 } // end anonymous namespace
 
 /// 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);
+    CloneTypeIIStmtDataCollector<FoldingSetNodeIDWrapper>(
+        S, Sequence.getASTContext(), OutputData);
 
     for (const Stmt *Child : S->children()) {
       if (!Child)
         continue;
 
       CollectStmtSequenceData(StmtSequence(Child, Sequence.getContainingDecl()),
                               OutputData);
     }
for (CloneDetector::CloneGroup &Group : Sequences) {
     // Generate hash codes for all children of S and save them in StmtsByHash.
     for (const StmtSequence &S : Group) {
       saveHash(S.front(), S.getContainingDecl(), StmtsByHash);
     }
 
     // Sort hash_codes in StmtsByHash.
     std::stable_sort(StmtsByHash.begin(), StmtsByHash.end(),
                      [](std::pair<size_t, StmtSequence> LHS,
-                            std::pair<size_t, StmtSequence> RHS) {
                        return LHS.first < RHS.first;
                      });
 
     // 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) {
size_t MinComplexityConstraint::calculateStmtComplexity(
   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);
+  std::string StartMacroStack =
+      data_collection::getMacroStack(Seq.getStartLoc(), Context);
+  std::string EndMacroStack =
+      data_collection::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

cfe/trunk/unittests/AST/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   Support
   )
 
 add_clang_unittest(ASTTests
   ASTContextParentMapTest.cpp
   ASTImporterTest.cpp
   ASTTypeTraitsTest.cpp
   ASTVectorTest.cpp
   CommentLexer.cpp
   CommentParser.cpp
+  DataCollectionTest.cpp
   DeclPrinterTest.cpp
   DeclTest.cpp
   EvaluateAsRValueTest.cpp
   ExternalASTSourceTest.cpp
   NamedDeclPrinterTest.cpp
   PostOrderASTVisitor.cpp
   SourceLocationTest.cpp
   StmtPrinterTest.cpp

cfe/trunk/unittests/AST/DataCollectionTest.cpp

+//===- unittests/AST/DataCollectionTest.cpp -------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file contains tests for the DataCollection module.
+//
+// They work by hashing the collected data of two nodes and asserting that the
+// hash values are equal iff the nodes are considered equal.
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/AST/DataCollection.h"
+#include "clang/AST/DeclTemplate.h"
+#include "clang/AST/StmtVisitor.h"
+#include "clang/ASTMatchers/ASTMatchFinder.h"
+#include "clang/Tooling/Tooling.h"
+#include "gtest/gtest.h"
+
+using namespace clang;
+using namespace tooling;
+using namespace ast_matchers;
+
+namespace {
+class StmtDataCollector : public ConstStmtVisitor<StmtDataCollector> {
+  ASTContext &Context;
+  llvm::MD5 &DataConsumer;
+
+  template <class T> void addData(const T &Data) {
+    data_collection::addDataToConsumer(DataConsumer, Data);
+  }
+
+public:
+  StmtDataCollector(const Stmt *S, ASTContext &Context, llvm::MD5 &DataConsumer)
+      : Context(Context), DataConsumer(DataConsumer) {
+    this->Visit(S);
+  }
+
+#define DEF_ADD_DATA(CLASS, CODE)                                              \
+  template <class Dummy = void> Dummy Visit##CLASS(const CLASS *S) {           \
+    CODE;                                                                      \
+    ConstStmtVisitor<StmtDataCollector>::Visit##CLASS(S);                      \
+  }
+
+#include "../../lib/AST/StmtDataCollectors.inc"
+};
+} // end anonymous namespace
+
+namespace {
+struct StmtHashMatch : public MatchFinder::MatchCallback {
+  unsigned NumFound;
+  llvm::MD5::MD5Result &Hash;
+  StmtHashMatch(llvm::MD5::MD5Result &Hash) : NumFound(0), Hash(Hash) {}
+
+  void run(const MatchFinder::MatchResult &Result) override {
+    const Stmt *S = Result.Nodes.getNodeAs<Stmt>("id");
+    if (!S)
+      return;
+    ++NumFound;
+    if (NumFound > 1)
+      return;
+    llvm::MD5 MD5;
+    StmtDataCollector(S, *Result.Context, MD5);
+    MD5.final(Hash);
+  }
+};
+} // end anonymous namespace
+
+static testing::AssertionResult hashStmt(llvm::MD5::MD5Result &Hash,
+                                         const StatementMatcher &StmtMatch,
+                                         StringRef Code) {
+  StmtHashMatch Hasher(Hash);
+  MatchFinder Finder;
+  Finder.addMatcher(StmtMatch, &Hasher);
+  std::unique_ptr<FrontendActionFactory> Factory(
+      newFrontendActionFactory(&Finder));
+  if (!runToolOnCode(Factory->create(), Code))
+    return testing::AssertionFailure()
+           << "Parsing error in \"" << Code.str() << "\"";
+  if (Hasher.NumFound == 0)
+    return testing::AssertionFailure() << "Matcher didn't find any statements";
+  if (Hasher.NumFound > 1)
+    return testing::AssertionFailure()
+           << "Matcher should match only one statement "
+              "(found "
+           << Hasher.NumFound << ")";
+  return testing::AssertionSuccess();
+}
+
+static testing::AssertionResult
+isStmtHashEqual(const StatementMatcher &StmtMatch, StringRef Code1,
+                StringRef Code2) {
+  llvm::MD5::MD5Result Hash1, Hash2;
+  testing::AssertionResult Result = hashStmt(Hash1, StmtMatch, Code1);
+  if (!Result)
+    return Result;
+  if (!(Result = hashStmt(Hash2, StmtMatch, Code2)))
+    return Result;
+
+  return testing::AssertionResult(Hash1 == Hash2);
+}
+
+TEST(StmtDataCollector, TestDeclRefExpr) {
+  ASSERT_TRUE(isStmtHashEqual(declRefExpr().bind("id"), "int x, r = x;",
+                              "int x, r = x;"));
+  ASSERT_FALSE(isStmtHashEqual(declRefExpr().bind("id"), "int x, r = x;",
+                               "int y, r = y;"));
+  ASSERT_FALSE(isStmtHashEqual(declRefExpr().bind("id"), "int x, r = x;",
+                               "namespace n { int x, r = x; };"));
+}
+
+TEST(StmtDataCollector, TestMemberExpr) {
+  ASSERT_TRUE(isStmtHashEqual(memberExpr().bind("id"),
+                              "struct { int x; } X; int r = X.x;",
+                              "struct { int x; } X; int r = (&X)->x;"));
+  ASSERT_TRUE(isStmtHashEqual(memberExpr().bind("id"),
+                              "struct { int x; } X; int r = X.x;",
+                              "struct { int x; } Y; int r = Y.x;"));
+  ASSERT_TRUE(isStmtHashEqual(memberExpr().bind("id"),
+                              "struct { int x; } X; int r = X.x;",
+                              "struct C { int x; } X; int r = X.C::x;"));
+  ASSERT_FALSE(isStmtHashEqual(memberExpr().bind("id"),
+                               "struct { int x; } X; int r = X.x;",
+                               "struct { int y; } X; int r = X.y;"));
+}
+
+TEST(StmtDataCollector, TestIntegerLiteral) {
+  ASSERT_TRUE(
+      isStmtHashEqual(integerLiteral().bind("id"), "int x = 0;", "int x = 0;"));
+  ASSERT_TRUE(
+      isStmtHashEqual(integerLiteral().bind("id"), "int x = 0;", "int x =00;"));
+  ASSERT_FALSE(
+      isStmtHashEqual(integerLiteral().bind("id"), "int x = 0;", "int x = 1;"));
+}
+
+TEST(StmtDataCollector, TestFloatingLiteral) {
+  ASSERT_TRUE(isStmtHashEqual(floatLiteral().bind("id"), "double x = .0;",
+                              "double x = .0;"));
+  ASSERT_TRUE(isStmtHashEqual(floatLiteral().bind("id"), "double x = .10;",
+                              "double x = .1;"));
+  ASSERT_TRUE(isStmtHashEqual(floatLiteral().bind("id"), "double x = .1;",
+                              "double x = 1e-1;"));
+  ASSERT_FALSE(isStmtHashEqual(floatLiteral().bind("id"), "double x = .0;",
+                               "double x = .1;"));
+}
+
+TEST(StmtDataCollector, TestStringLiteral) {
+  ASSERT_TRUE(isStmtHashEqual(stringLiteral().bind("id"), R"(char x[] = "0";)",
+                              R"(char x[] = "0";)"));
+  ASSERT_FALSE(isStmtHashEqual(stringLiteral().bind("id"), R"(char x[] = "0";)",
+                               R"(char x[] = "1";)"));
+}
+
+TEST(StmtDataCollector, TestCXXBoolLiteral) {
+  ASSERT_TRUE(isStmtHashEqual(cxxBoolLiteral().bind("id"), "bool x = false;",
+                              "bool x = false;"));
+  ASSERT_FALSE(isStmtHashEqual(cxxBoolLiteral().bind("id"), "bool x = false;",
+                               "bool x = true;"));
+}
+
+TEST(StmtDataCollector, TestCharacterLiteral) {
+  ASSERT_TRUE(isStmtHashEqual(characterLiteral().bind("id"), "char x = '0';",
+                              "char x = '0';"));
+  ASSERT_TRUE(isStmtHashEqual(characterLiteral().bind("id"),
+                              R"(char x = '\0';)",
+                              R"(char x = '\x00';)"));
+  ASSERT_FALSE(isStmtHashEqual(characterLiteral().bind("id"), "char x = '0';",
+                               "char x = '1';"));
+}