[analyzer] Make CloneDetector consider macro expansions.

So far macro-generated code was treated by the CloneDetector as normal code.
This caused that some macros where reported as false-positive clones because
large chunks of code coming from otherwise concise macro expansions were treated
as copy-pasted code.

This patch ensures that macros are treated in the same way as literals/function
calls. This prevents macros that expand into multiple statements
from being reported as clones.

Patch by Raphael Isemann!

Differential Revision: https://reviews.llvm.org/D23316


git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@279367 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 67 insertions, 4 deletions

diff --git a/lib/Analysis/CloneDetection.cpp b/lib/Analysis/CloneDetection.cpp
index ee1c6943f2..9bba611d0a 100644
--- a/lib/Analysis/CloneDetection.cpp
+++ b/lib/Analysis/CloneDetection.cpp
@@ -17,7 +17,9 @@
 #include "clang/AST/RecursiveASTVisitor.h"
 #include "clang/AST/Stmt.h"
 #include "clang/AST/StmtVisitor.h"
+#include "clang/Lex/Lexer.h"
 #include "llvm/ADT/StringRef.h"
+#include "llvm/Support/raw_ostream.h"
 
 using namespace clang;
 
@@ -239,6 +241,38 @@ public:
 };
 }
 
+/// \brief Prints the macro name that contains the given SourceLocation into
+///        the given raw_string_ostream.
+static void printMacroName(llvm::raw_string_ostream &MacroStack,
+                           ASTContext &Context, SourceLocation Loc) {
+  MacroStack << Lexer::getImmediateMacroName(Loc, Context.getSourceManager(),
+                                             Context.getLangOpts());
+
+  // Add an empty space at the end as a padding to prevent
+  // that macro names concatenate to the names of other macros.
+  MacroStack << " ";
+}
+
+/// \brief Returns a string that represents all macro expansions that
+///        expanded into the given SourceLocation.
+///
+/// If 'getMacroStack(A) == getMacroStack(B)' is true, then the SourceLocations
+/// A and B are expanded from the same macros in the same order.
+static std::string getMacroStack(SourceLocation Loc, ASTContext &Context) {
+  std::string MacroStack;
+  llvm::raw_string_ostream MacroStackStream(MacroStack);
+  SourceManager &SM = Context.getSourceManager();
+
+  // Iterate over all macros that expanded into the given SourceLocation.
+  while (Loc.isMacroID()) {
+    // Add the macro name to the stream.
+    printMacroName(MacroStackStream, Context, Loc);
+    Loc = SM.getImmediateMacroCallerLoc(Loc);
+  }
+  MacroStackStream.flush();
+  return MacroStack;
+}
+
 namespace {
 /// \brief Collects the data of a single Stmt.
 ///
@@ -299,7 +333,13 @@ public:
     ConstStmtVisitor<StmtDataCollector>::Visit##CLASS(S);                      \
   }
 
-  DEF_ADD_DATA(Stmt, { addData(S->getStmtClass()); })
+  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 ----------------------------------------------//
@@ -434,14 +474,36 @@ class CloneSignatureGenerator {
   /// tree and stores them in the CloneDetector.
   ///
   /// \param S The root of the given statement tree.
+  /// \param ParentMacroStack A string representing the macros that generated
+  ///                         the parent statement or an empty string if no
+  ///                         macros generated the parent statement.
+  ///                         See getMacroStack() for generating such a string.
   /// \return The CloneSignature of the root statement.
-  CloneDetector::CloneSignature generateSignatures(const Stmt *S) {
+  CloneDetector::CloneSignature
+  generateSignatures(const Stmt *S, const std::string &ParentMacroStack) {
     // Create an empty signature that will be filled in this method.
     CloneDetector::CloneSignature Signature;
 
     // Collect all relevant data from S and put it into the empty signature.
     StmtDataCollector(S, Context, Signature.Data);
 
+    // Look up what macros expanded into the current statement.
+    std::string StartMacroStack = getMacroStack(S->getLocStart(), Context);
+    std::string EndMacroStack = getMacroStack(S->getLocEnd(), Context);
+
+    // First, check if ParentMacroStack is not empty which means we are currently
+    // dealing with a parent statement which was expanded from a macro.
+    // If this parent statement was expanded from the same macros as this
+    // statement, we reduce the initial complexity of this statement to zero.
+    // This causes that a group of statements that were generated by a single
+    // macro expansion will only increase the total complexity by one.
+    // Note: This is not the final complexity of this statement as we still
+    // add the complexity of the child statements to the complexity value.
+    if (!ParentMacroStack.empty() && (StartMacroStack == ParentMacroStack &&
+                                      EndMacroStack == ParentMacroStack)) {
+      Signature.Complexity = 0;
+    }
+
     // 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;
@@ -457,7 +519,8 @@ class CloneSignatureGenerator {
 
       // 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);
+      // We pass only the StartMacroStack along to keep things simple.
+      auto ChildSignature = generateSignatures(Child, StartMacroStack);
 
       // Add the collected data to the signature of the current statement.
       Signature.add(ChildSignature);
@@ -518,7 +581,7 @@ public:
       : CD(CD), Context(Context) {}
 
   /// \brief Generates signatures for all statements in the given function body.
-  void consumeCodeBody(const Stmt *S) { generateSignatures(S); }
+  void consumeCodeBody(const Stmt *S) { generateSignatures(S, ""); }
 };
 } // end anonymous namespace