[clang-tidy] Fix a false positive in misc-redundant-expression check

[dkrupp]

Summary

Do not warn for redundant conditional expressions
when the true and false branches are expanded from
different macros even when they are
defined by one another.

We used to get a false warning in the following case:

#define M1 1
#define M2 M1
int test(int cond) {
 return cond ? M1 : M2; // false warning: 'true' and 'false' expressions are equivalent
}

The problem was that the Lexer::getImmediateMacroName() call was used for comparing macros, which returned "M1" for the expansion of M1 and M2.
Now we are comparing macros from token to token.

[Szelethus]

@JonasToth this is the Lexer based expression equality check I talked about in D54757#1311516. The point of this patch is that the definition is a macro sure could be build dependent, but the macro name is not, so it wouldn't warn on the case I showed. What do you think?

[JonasToth]

In D55125#1314741, @Szelethus wrote:

@JonasToth this is the Lexer based expression equality check I talked about in D54757#1311516. The point of this patch is that the definition is a macro sure could be build dependent, but the macro name is not, so it wouldn't warn on the case I showed. What do you think?

Yes, this approach is possible.
IMHO it is still a bug/redudant if you do the same thing on both paths and warning on it makes the programmer aware of the fact. E.g. the macros might have been something different before, but a refactoring made them equal and resulted in this situation.

clang-tidy/misc/RedundantExpressionCheck.cpp

601

Please run clang-format

631

clang:: should not be necessary here, is it? SourceLocation and other types are access without namespace, too.

test/clang-tidy/misc-redundant-expression.cpp

109

Could you please add a test where the macro is undefed and redefined to something else?

[Szelethus]

I see your point, but here's why I think it isn't a bug: I like to see macros as constexpr variables, and if I used those instead, I personally wouldn't like to get a warning just because they have the same value. In C, silencing such a warning isn't even really possible.

Another interesting thought, @donat.nagy's check works by comparing actual nodes of the AST, while this one would work with Lexer, but they almost want to do the same thing, the only difference is that the first checks whether two pieces of code are equivalent, and the second checks whether they are the same. Maybe it'd be worth to extract the logic into a simple areStmtsEqual(const Stmt *S1, const Stmt *S2, bool ShouldCompareLexically = false) function, that would do AST based comparison if the last param is set to false, and would use Lexer if set to true. After that, we could just add command line options to both of these checks, to leave it up to the user to choose in between them. Maybe folks who suffer from heavily macro-infested code would rather bear the obvious performance hit Lexer causes for little more precise warnings, and (for example) users of C++11 (because there are few excuses not to prefer constexpr there) could run in AST mode.

edit: I'm not actually all that sure about the performance hit. Just a guess.

But I'm just thinking aloud really.

[dkrupp]

-clang-format applied
-clang:: namespace qualifiers removed

[dkrupp]

In D55125#1314788, @JonasToth wrote:

In D55125#1314741, @Szelethus wrote:

@JonasToth this is the Lexer based expression equality check I talked about in D54757#1311516. The point of this patch is that the definition is a macro sure could be build dependent, but the macro name is not, so it wouldn't warn on the case I showed. What do you think?

Yes, this approach is possible.
IMHO it is still a bug/redudant if you do the same thing on both paths and warning on it makes the programmer aware of the fact. E.g. the macros might have been something different before, but a refactoring made them equal and resulted in this situation.

@JonasThoth: I see you point with refactoring, but let's imagine that the two macros COND_OP_MACRO and COND_OP_THIRD_MACRO are defined by compile time parameters. If the two macros are happened to be defined to the same value the user would get a warning, and if not she would not. How would the user would "fix" her code in the first case? So if the macro names are different in the conditional expression, it is not a redundant expression because the macro names are compile time parameters (with just eventually same values). This was the same logic the old test case were testing: k += (y < 0) ? COND_OP_MACRO : COND_OP_OTHER_MACRO;

test/clang-tidy/misc-redundant-expression.cpp

109

I am not sure what you exactly suggest here. It should not matter what COND_OP_THIRD_MACRO is defined to as we lexically compare tokens as they are written in the original source code.

Could you be a bit more specific what test case you would like to add?

[dkrupp]

In D55125#1315335, @Szelethus wrote:

I see your point, but here's why I think it isn't a bug: I like to see macros as constexpr variables, and if I used those instead, I personally wouldn't like to get a warning just because they have the same value. In C, silencing such a warning isn't even really possible.

Another interesting thought, @donat.nagy's check works by comparing actual nodes of the AST, while this one would work with Lexer, but they almost want to do the same thing, the only difference is that the first checks whether two pieces of code are equivalent, and the second checks whether they are the same. Maybe it'd be worth to extract the logic into a simple areStmtsEqual(const Stmt *S1, const Stmt *S2, bool ShouldCompareLexically = false) function, that would do AST based comparison if the last param is set to false, and would use Lexer if set to true. After that, we could just add command line options to both of these checks, to leave it up to the user to choose in between them. Maybe folks who suffer from heavily macro-infested code would rather bear the obvious performance hit Lexer causes for little more precise warnings, and (for example) users of C++11 (because there are few excuses not to prefer constexpr there) could run in AST mode.

edit: I'm not actually all that sure about the performance hit. Just a guess.

But I'm just thinking aloud really.

Wiring out the lexical comparison and AST based comparison sounds like an interesting idea, however IMHO such a setting is too coarse-grained on the file level. My guess would be that it depends from expression (fragment) to expression fragment how you want to compare them: for macros lexical comparison is better, for arithmetic expressions with many parentheses AST based recursive comparison may be a better fit (as implemented also in this checker).

[JonasToth]

Wiring out the lexical comparison and AST based comparison sounds like an interesting idea, however IMHO such a setting is too coarse-grained on the file level. My guess would be that it depends from expression (fragment) to expression fragment how you want to compare them: for macros lexical comparison is better, for arithmetic expressions with many parentheses AST based recursive comparison may be a better fit (as implemented also in this checker).

Yes, I agree. I think having such a utility would make sense as an future addition, but I would not like to block on it for several reasons:

• do we know how often it this case even appears?
• is it a real false positive in all cases?
• it can be silence with // NOLINT if it actually is a false-positive

My gut feeling is that its rather a corner-case (this late patch to misc-redundant-expression is somewhat indicative for it) and would block the patch from landing.
Allowing future room for flexibility is certainly good.

test/clang-tidy/misc-redundant-expression.cpp

109

*should* not matter is my point, please show that :)

[Szelethus]

Yup, I agree with everything that was said.

[dkrupp]

new undef/defined testcase added

[dkrupp]

test/clang-tidy/misc-redundant-expression.cpp

109

undef/define testcase added and passes. @JonasToth is this what you thought of?

[JonasToth]

clang-tidy/misc/RedundantExpressionCheck.cpp

605

This operation could overflow if len(T1) > len(T2) and T2 is the last token of the file. I think std::min(T1.getLength(), T2.getLength()) would be better.

608

Nit: Please add whitespace after and use / for the function documentation.

629

Please format with clang-format, some places seem to be a little off whitespace-wise.

test/clang-tidy/misc-redundant-expression.cpp

109

yup. thank you

[alexfh]

clang-tidy/misc/RedundantExpressionCheck.cpp

601

Should this function compare token kinds first?

602

Token::getLength() will assert-fail for annotation tokens.

605

This code is only executed when they have the same length.

[Szelethus]

clang-tidy/misc/RedundantExpressionCheck.cpp

601

I personally prefer to see boolean functions to have a name that starts with either "should", "is", "does", "has", or anything that clearly indicates that it returns with either true or false. In this case, "compare" is especially misleading, since it might as well return -1, 0 or 1.

Maybe hasSameLength?

602

I guess if T1.isNot(tok::raw_identifier) (or T2) we could get away with simply comparing token kinds. If they are, it wouldn't assert. :)

638

It seems like we're only checking whether these values are 0 or not, maybe make them bool? Also, I find Rem a little cryptic, what is it referring to? Maybe RemainingCharCount?

Maybe we should just make a simple function, so we could both boost readability, and get rid of some these variables (LLoc, RLoc) entirely:

unsinged getCharCountUntilEndOfExpr(SourceRange ExprSR, Token T,
                                    const SourceManager &SM) {

  assert((ExprSR.getBegin() > T.getLocation() ||
          ExprSR.getEnd() < T.getLocation()) &&
         "Token is not within the expression range!");

  return SM.getCharacterData(SM.getExpansionLoc(ExprSR.getEnd())) -
         SM.getCharacterData(T.getLocation());
}

[Szelethus]

clang-tidy/misc/RedundantExpressionCheck.cpp

601

Sorry, upon closer inspection, isSameToken would be more fitting. Mind you, there already is a function somewhere for this, but due to the lack of a Preprocessor object, we can't use it.
https://clang.llvm.org/doxygen/RewriteMacros_8cpp.html#a0ba058873ae3930f71b19b4dee4b1cbb

[dkrupp]

All comments fixed.

I also added the handling of redundancy comparison of sizeof(..), alignof() operators.

[dkrupp]

Thanks for your comments. I fixed them all. I also added the handling of redundant sizeof() and alignof() operators on the way. Please check if OK now...

clang-tidy/misc/RedundantExpressionCheck.cpp

602

I changed to code as per the suggestion from Szelethus.
So we will compare only raw_identifiers char-by-char, the rest by kind only.
According to my tests, macros and types, typedefs for example are such raw_identifiers.

605

exactly, overflow should not happen.

638

good point. Refactored ass suggested.

[alexfh]

clang-tidy/misc/RedundantExpressionCheck.cpp

136

Any reasons not to pull out the results of cast<>() to local variables? In this particular case this would make the code look much simpler.

601

const Token&

602

clang-format, please

604

https://llvm.org/docs/CodingStandards.html#don-t-use-else-after-a-return

642–643

Can you just compare the location of (the end of?) the token with the end of the range?

[dkrupp]

Thanks for your reviews!
I have fixed all your comments and rebased the patch to the latest master.

[aaron.ballman]

clang-tidy/misc/RedundantExpressionCheck.cpp

136–138

const auto * since you already spell the type in the initializer.

833

Not that I oppose the cleanup, but there are a bunch of these kinds of changes that are orthogonal to the patch. Feel free to commit these cleanups as an NFC commit and then rebase on top of it if you'd like, but they shouldn't be in this patch.

[dkrupp]

@aaron.ballman 's comments are fixed.

[aaron.ballman]

clang-tidy/misc/RedundantExpressionCheck.cpp

601

isSameRawIdentifierToken() so that the name isn't too generic.

609–610

I would feel more comfortable if this were written:

return StringRef(SM.getCharacterData(T1.getLocation()), T1.getLength()) == StringRef(SM.getCharacterData(T2.getLocation()), T2.getLength());

644

You can drop a set of parens here as they don't change the order of evaluation.

test/clang-tidy/misc-redundant-expression.cpp

137

Spurious newline.

[alexfh]

One more nit.

clang-tidy/misc/RedundantExpressionCheck.cpp

644

I'd propagate the negation into the parentheses. I find it easier to understand !a || !b || !c than !(a && b && c), since the former can be digested piece by piece, but the latter requires the reader to keep the ! in their mind and "recurse" into the nested parentheses. It's similar to the "early return" pattern vs. nested conditional statements.

[dkrupp]

Thanks @aaron.ballman and @alexfh for your review.
I fixed your findings.

[aaron.ballman]

LGTM!

[dkrupp]

@aaron.ballman could you please commit?
I don't have commit access. Thx.

[aaron.ballman]

In D55125#1704397, @dkrupp wrote:

@aaron.ballman could you please commit?
I don't have commit access. Thx.

I'm happy to do so, but the patch does not apply cleanly to trunk. Can you rebase? (Sorry for the delayed on applying the patch, I was traveling last week and didn't have access to the repo.)

[dkrupp]

The patch is rebased to the latest master.

[dkrupp]

@aaron.ballman could you please check now? Thanks!

[aaron.ballman]

In D55125#1717910, @dkrupp wrote:

@aaron.ballman could you please check now? Thanks!

Sorry for the delay, but I've committed this on your behalf in 1caa66d0759f6bd0851a40645afac8e8a7f84341

clang-tidy/misc/RedundantExpressionCheck.cpp

case Stmt::UnaryOperatorClass:
     if (cast<UnaryOperator>(Left)->isIncrementDecrementOp())
       return false;
     return cast<UnaryOperator>(Left)->getOpcode() ==
            cast<UnaryOperator>(Right)->getOpcode();
   case Stmt::BinaryOperatorClass:
     return cast<BinaryOperator>(Left)->getOpcode() ==
            cast<BinaryOperator>(Right)->getOpcode();
   }
 }
 
 // For a given expression 'x', returns whether the ranges covered by the
 // relational operators are equivalent (i.e.  x <= 4 is equivalent to x < 5).
 static bool areEquivalentRanges(BinaryOperatorKind OpcodeLHS,
                                 const APSInt &ValueLHS,
                                 BinaryOperatorKind OpcodeRHS,
                                 const APSInt &ValueRHS) {
   assert(APSInt::compareValues(ValueLHS, ValueRHS) <= 0 &&
          "Values must be ordered");
   // Handle the case where constants are the same: x <= 4  <==>  x <= 4.
static bool retrieveConstExprFromBothSides(const BinaryOperator *&BinOp,
   assert(BinOpLhs->getOpcode() == BinOpRhs->getOpcode() &&
          "Sides of the binary operator must be equivalent expressions!");
 
   SideOpcode = BinOpLhs->getOpcode();
 
   return true;
 }
 
+static bool compareToks(Token &T1, Token &T2, const SourceManager &SM) {
+  if (T1.getLength() != T2.getLength())
+    return false;
+  return strncmp(SM.getCharacterData(T1.getLocation()),
+                 SM.getCharacterData(T2.getLocation()), T1.getLength()) == 0;
+}
+
+//Returns true if both LhsEpxr and RhsExpr are
+//macro expressions and they are expanded
+//from different macros.
 static bool areExprsFromDifferentMacros(const Expr *LhsExpr,
                                         const Expr *RhsExpr,
                                         const ASTContext *AstCtx) {
   if (!LhsExpr || !RhsExpr)
     return false;
-
-  SourceLocation LhsLoc = LhsExpr->getExprLoc();
-  SourceLocation RhsLoc = RhsExpr->getExprLoc();
-
-  if (!LhsLoc.isMacroID() || !RhsLoc.isMacroID())
+  SourceRange Lsr = LhsExpr->getSourceRange();
+  SourceRange Rsr = RhsExpr->getSourceRange();
+  if (!Lsr.getBegin().isMacroID() || !Rsr.getBegin().isMacroID())
     return false;
-
   const SourceManager &SM = AstCtx->getSourceManager();
   const LangOptions &LO = AstCtx->getLangOpts();
 
-  return !(Lexer::getImmediateMacroName(LhsLoc, SM, LO) ==
-          Lexer::getImmediateMacroName(RhsLoc, SM, LO));
+  std::pair<FileID, unsigned> LsrLocInfo =
+      SM.getDecomposedLoc(SM.getExpansionLoc(Lsr.getBegin()));
+  std::pair<FileID, unsigned> RsrLocInfo =
+      SM.getDecomposedLoc(SM.getExpansionLoc(Rsr.getBegin()));
+  const llvm::MemoryBuffer *MB = SM.getBuffer(LsrLocInfo.first);
+
+  const char *LTokenPos = MB->getBufferStart() + LsrLocInfo.second;
+  const char *RTokenPos = MB->getBufferStart() + RsrLocInfo.second;
+  Lexer LRawLex(SM.getLocForStartOfFile(LsrLocInfo.first), LO,
+                       MB->getBufferStart(), LTokenPos, MB->getBufferEnd());
+  Lexer RRawLex(SM.getLocForStartOfFile(RsrLocInfo.first), LO,
+                       MB->getBufferStart(), RTokenPos, MB->getBufferEnd());
+
+  Token LTok, RTok;
+  SourceLocation LLoc, RLoc;
+  int LRem, RRem;
+  do {//we compare the expressions token-by-token
+    LRawLex.LexFromRawLexer(LTok);
+    RRawLex.LexFromRawLexer(RTok);
+    LLoc = LTok.getLocation();
+    RLoc = RTok.getLocation();
+    LRem = SM.getCharacterData(SM.getExpansionLoc(Lsr.getEnd())) -
+           SM.getCharacterData(LLoc);//remaining characters until the end of expr
+    RRem = SM.getCharacterData(SM.getExpansionLoc(Rsr.getEnd())) -
+           SM.getCharacterData(RLoc);
+  } while (!LTok.is(tok::eof) && !RTok.is(tok::eof) &&
+           compareToks(LTok, RTok, SM) && LRem > 0 && RRem > 0);
+  return !((LRem == 0 && RRem == 0) && compareToks(LTok, RTok, SM));
 }
 
 static bool areExprsMacroAndNonMacro(const Expr *&LhsExpr,
                                      const Expr *&RhsExpr) {
   if (!LhsExpr || !RhsExpr)
     return false;
 
   SourceLocation LhsLoc = LhsExpr->getExprLoc();
static bool exprEvaluatesToBitwiseNegatedZero(BinaryOperatorKind Opcode,
   return (Opcode == BO_Or || Opcode == BO_OrAssign) && ~Value == 0;
 }
 
 static bool exprEvaluatesToSymbolic(BinaryOperatorKind Opcode, APSInt Value) {
   return ((Opcode == BO_Or || Opcode == BO_OrAssign) && Value == 0) ||
          ((Opcode == BO_And || Opcode == BO_AndAssign) && ~Value == 0);
 }
 
 
 void RedundantExpressionCheck::checkBitwiseExpr(
     const MatchFinder::MatchResult &Result) {
   if (const auto *ComparisonOperator = Result.Nodes.getNodeAs<BinaryOperator>(
           "binop-const-compare-to-const")) {
     BinaryOperatorKind Opcode = ComparisonOperator->getOpcode();
 
     APSInt LhsValue, RhsValue;
     const Expr *LhsSymbol = nullptr;

test/clang-tidy/misc-redundant-expression.cpp

int Valid(int X, int Y) {
 
   if ("abc" == "ABC") return 1;
   if (foo(bar(0)) < (foo(bat(0, 1)))) return 1;
   return 0;
 }
 
 #define COND_OP_MACRO 9
 #define COND_OP_OTHER_MACRO 9
+#define COND_OP_THIRD_MACRO COND_OP_MACRO
 int TestConditional(int x, int y) {
   int k = 0;
   k += (y < 0) ? x : x;
   // CHECK-MESSAGES: :[[@LINE-1]]:20: warning: 'true' and 'false' expressions are equivalent
   k += (y < 0) ? x + 1 : x + 1;
   // CHECK-MESSAGES: :[[@LINE-1]]:24: warning: 'true' and 'false' expressions are equivalent
   k += (y < 0) ? COND_OP_MACRO : COND_OP_MACRO;
   // CHECK-MESSAGES: :[[@LINE-1]]:32: warning: 'true' and 'false' expressions are equivalent
+  k += (y < 0) ? COND_OP_MACRO + COND_OP_OTHER_MACRO : COND_OP_MACRO + COND_OP_OTHER_MACRO;
+  // CHECK-MESSAGES: :[[@LINE-1]]:54: warning: 'true' and 'false' expressions are equivalent
 
   // Do not match for conditional operators with a macro and a const.
   k += (y < 0) ? COND_OP_MACRO : 9;
   // Do not match for conditional operators with expressions from different macros.
   k += (y < 0) ? COND_OP_MACRO : COND_OP_OTHER_MACRO;
+  // Do not match for conditional operators when a macro is defined to another macro
+  k += (y < 0) ? COND_OP_MACRO : COND_OP_THIRD_MACRO;
+#undef COND_OP_THIRD_MACRO
+#define   COND_OP_THIRD_MACRO 8
+  k += (y < 0) ? COND_OP_MACRO : COND_OP_THIRD_MACRO;
+#undef COND_OP_THIRD_MACRO
+
   return k;
 }
 #undef COND_OP_MACRO
 #undef COND_OP_OTHER_MACRO
 
+
 // Overloaded operators that compare two instances of a struct.
 struct MyStruct {
   int x;  
   bool operator==(const MyStruct& rhs) const {return this->x == rhs.x; } // not modifing
   bool operator>=(const MyStruct& rhs) const { return this->x >= rhs.x; } // not modifing
   bool operator<=(MyStruct& rhs) const { return this->x <= rhs.x; }
   bool operator&&(const MyStruct& rhs){ this->x++; return this->x && rhs.x; }
 } Q;