[analyzer] Fixed the false-positives caused by macro generated code.

[teemperor]

Summary

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 their generated code was detected as a clone.

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

[v.g.vassilev]

lib/Analysis/CloneDetection.cpp

431

What are complex macros? Could you clarify?

test/Analysis/copypaste/macro-complexity.cpp

19

I am not sure I understand this comment. Could you reword?

test/Analysis/copypaste/macros.cpp

11

Wouldn't it be a good idea to have a fixit hint, saying "Did you mean to use ABS(a,b)". If the suggestion is applied, it would make the code more consistent, however it would encourage using preprocessor tricks (which is not always considered as good practice).

[omtcyfz]

lib/Analysis/CloneDetection.cpp

436

Do I understand correctly that a code generated by a macro doesn't affect "complexity" at all then?

TEST_F(QueryParserTest, Complete) {
  std::vector<llvm::LineEditor::Completion> Comps =
      QueryParser::complete("", 0, QS);
  ASSERT_EQ(6u, Comps.size());
  EXPECT_EQ("help ", Comps[0].TypedText);
  EXPECT_EQ("help", Comps[0].DisplayText);
  EXPECT_EQ("let ", Comps[1].TypedText);
  EXPECT_EQ("let", Comps[1].DisplayText);
  EXPECT_EQ("match ", Comps[2].TypedText);
  EXPECT_EQ("match", Comps[2].DisplayText);
  EXPECT_EQ("set ", Comps[3].TypedText);
  EXPECT_EQ("set", Comps[3].DisplayText);
  EXPECT_EQ("unlet ", Comps[4].TypedText);
  EXPECT_EQ("unlet", Comps[4].DisplayText);
  EXPECT_EQ("quit", Comps[5].DisplayText);
  EXPECT_EQ("quit ", Comps[5].TypedText);

  Comps = QueryParser::complete("set o", 5, QS);
  ASSERT_EQ(1u, Comps.size());
  EXPECT_EQ("utput ", Comps[0].TypedText);
  EXPECT_EQ("output", Comps[0].DisplayText);

  Comps = QueryParser::complete("match while", 11, QS);
  ASSERT_EQ(1u, Comps.size());
  EXPECT_EQ("Stmt(", Comps[0].TypedText);
  EXPECT_EQ("Matcher<Stmt> whileStmt(Matcher<WhileStmt>...)",
            Comps[0].DisplayText);
}

This is an actual piece of code from extra/unittests/clang-query/QueryParserTest.cpp. Yes, it is a test, but it still is a nice example of how many macros can be found in code (especially if we are talking about pure C or some weird C++).

Thus, I think it is reasonable to treat macro invocation as a 1-"complexity" node.

[NoQ]

lib/Analysis/CloneDetection.cpp

436

This "0" is not for the macro itself, but for the statements into which it expands. Macro itself is not a statement. If we put "1" here, it would produce a lot more complexity than you want.

That said, it's a good idea to treat every macro as a "complexity-1" statement, just need to figure out how to implement that correctly :)

Perhaps scan the source range of the sequence for how many different macro expansions are included, and add that number to complexity(?)

[omtcyfz]

lib/Analysis/CloneDetection.cpp

436

This "0" is not for the macro itself, but for the statements into which it expands. Macro itself is not a statement. If we put "1" here, it would produce a lot more complexity than you want.

Sure, I understand that, this is why I didn't suggest putting 1 there.

Perhaps scan the source range of the sequence for how many different macro expansions are included, and add that number to complexity(?)

Yes, this is exactly the solution that would work. Since macros aren't in the AST we'd need to get through SourceRange anyway.

[omtcyfz]

lib/Analysis/CloneDetection.cpp

436

Though, it has to be optimized in order to prevent parsing a SourceLocation multiple times.

[omtcyfz]

lib/Analysis/CloneDetection.cpp

436

*visiting each SourceLocation

[NoQ]

No comments of my own, the patch looks good :)

lib/Analysis/CloneDetection.cpp

436

Yeah, as a rough approximation we could count macro expansions within the current statement's children...

test/Analysis/copypaste/macro-complexity.cpp

19

Without macros, the same code would constitute a complex clone.
Wrapping code into macros reduces complexity of the code.
This tests the test above.

^(tried out some reword-ings)

[teemperor]

• Added more documentation to the CloneSignature::Complexity field.
• Macros now have a complexity value of 1 + sum(ChildComplexityValues).
• Tests should be less cryptic now.

[teemperor]

lib/Analysis/CloneDetection.cpp

436

I'm now checking all expanded macros of the start/end locations. This should handle everything if I see that correctly (beside empty non-function macros which I marked as false-positives - not sure how we best handle them).

test/Analysis/copypaste/macros.cpp

11

I don't think detecting clones between macro definitions and normal code is easily possible. Doing the same for functions however is certainly possible (i.e. "did you meant to call max(a, b)). I added that to the open points list.

[teemperor]

• Added false-positives note for empty macros to the test suite.

[teemperor]

• Fixed typo.

lib/Analysis/CloneDetection.cpp

 // 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()); })
+  DEF_ADD_DATA(Stmt, {
+    addData(S->getStmtClass());
+    // This ensures that macro-code and non-macro code never lands in the same
+    // hash group. This is necessary as they have different complexity values
+    // and a single group currently needs to have one common complexity value.
+    addData(S->getLocStart().isMacroID());
+    addData(S->getLocEnd().isMacroID());
+  })
   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());

   /// \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;
 
     // Collect all relevant data from S and put it into the empty signature.
     StmtDataCollector(S, Context, Signature.Data);
 
+    // If this code is generated by a macro, it won't increase the complexity
+    // level of it's containing clone. This prevents false-positives caused by
+    // complex macros. For example 'assert(false)' could be reported as a clone
+    // if the assert macro is implemented as a expression that would
+    // fulfill the standard complexity requirement for clones.
+    bool IsInMacro = S->getLocStart().isMacroID() || S->getLocEnd().isMacroID();
+    if (IsInMacro) {
+      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;
     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.

test/Analysis/copypaste/macro-complexity.cpp

+// RUN: %clang_cc1 -analyze -std=c++11 -analyzer-checker=alpha.clone.CloneChecker -analyzer-config alpha.clone.CloneChecker:MinimumCloneComplexity=20 -verify %s
+
+// Tests that only non-generated code increases the complexity of a statement.
+
+#define MACRO_FOO(a, b) a > b ? -a * a : -b * b;
+
+// The body of these two aren't complex enough to be considered clones of each
+// other.
+int fooMacro(int a, int b) {
+  return MACRO_FOO(a, b);
+}
+
+int fooMacroClone(int a, int b) {
+  return MACRO_FOO(a, b);
+}
+
+// This tests that above code would be complex enough to be reported.
+// Prevents that this tests won't accidentially pass because the code inside
+// the macro isn't complex enough.
+int foo(int a, int b) {  // expected-warning{{Detected code clone.}}
+  return a > b ? -a * a : -b * b;
+}
+
+int fooClone(int a, int b) {  // expected-note{{Related code clone is here.}}
+  return a > b ? -a * a : -b * b;
+}

test/Analysis/copypaste/macros.cpp

+// RUN: %clang_cc1 -analyze -std=c++11 -analyzer-checker=alpha.clone.CloneChecker -verify %s
+
+// Tests that macros and non-macro clones aren't mixed into the same hash
+// group. This is currently necessary as all clones in a hash group need
+// to have the same complexity value. Macros have smaller complexity values
+// and need to be in their own hash group.
+
+#define ABS(a, b) a > b ? a : b;
+
+int max(int a, int b) { // expected-warning{{Detected code clone.}}
+  return a > b ? a : b;
+}
+
+int maxClone(int a, int b) { // expected-note{{Related code clone is here.}}
+  return a > b ? a : b;
+}
+
+int maxNoClone(int a, int b) {
+  return ABS(a, b);
+}
+
+// Tests that code containing macros is still reported.
+
+void longFoo() { // expected-warning{{Detected code clone.}}
+  const unsigned size = 10;
+  int array[size];
+  for (unsigned i = 0; i < size; i++) {
+    array[i] = ABS(i, 5);
+  }
+}
+
+void longFooClone () { // expected-note{{Related code clone is here.}}
+  const unsigned size = 10;
+  int array[size];
+  for (unsigned i = 0; i < size; i++) {
+    array[i] = ABS(i, 5);
+  }
+}