[clang-tidy] Misc redundant expression checker updated for ineffective bitwise operator expressions

[barancsuk]

Summary

Redundant Expression Checker is updated to find ineffective or redundant bitwise operator expressions.

The checker targets bitwise operator expressions with a symbolic expression and an integer literal as operands, where the expression always evaluates to the same numeric constant or leaves the symbolic expression unaltered.

Examples:

• Always evaluates to 0:

int X;
if(0 & X) return;

• Always evaluates to ~0:

int Y;
if(Y | ~0) return;

• The symbol is unmodified:

int Z;
Z &= ~0;

The checker matches bitwise OR, bitwise AND and their corresponding assignment operators.

[xazax.hun]

I really like these additions. Found some nits otherwise looks good.

clang-tidy/misc/RedundantExpressionCheck.cpp

953 ↗

(On Diff #120235)

Maybe this could be called like exprEvaluatesToConstant, since it might actually be evaluated to zero based on the other operand, right?

954 ↗

(On Diff #120235)

The parens around ~Value are redundant.

959 ↗

(On Diff #120235)

Maybe I would name this differently, like exprIdempotentOperation.

962 ↗

(On Diff #120235)

Same as above.

1012 ↗

(On Diff #120235)

Redundant parens here as well.

1026 ↗

(On Diff #120235)

The ConstExprText is not quoted in the error message.

[xazax.hun]

clang-tidy/misc/RedundantExpressionCheck.cpp

959 ↗

(On Diff #120235)

Never mind, Idempotent is not the correct term here.

[Eugene.Zelenko]

It'll be good idea to mention improvement in Release Notes.

[barancsuk]

Address review comments

[barancsuk]

clang-tidy/misc/RedundantExpressionCheck.cpp

953 ↗

(On Diff #120235)

The 'not zero' in the function name means a 'bitwise not zero' or 'negated zero' (~0), which has a bit representation containing only ones.

The function itself checks whether this value is used in a bitwise OR expression as an operand, because in this case the expression always evaluates to ~0 independently from the other operand's value.

I changed the function name to exprEvaluatesToNegatedZero.

[xazax.hun]

clang-tidy/misc/RedundantExpressionCheck.cpp

885 ↗

(On Diff #120948)

I would eliminate this local variable, it does not convey additional information. Also, it does not start with a capital letter.

895 ↗

(On Diff #120948)

Same as above.

[barancsuk]

Address latest review comments

[xazax.hun]

clang-tidy/misc/RedundantExpressionCheck.cpp

142 ↗

(On Diff #121500)

I would eliminate this new line.

143 ↗

(On Diff #121500)

Please initialize this variable.

147 ↗

(On Diff #121500)

Maybe you could ignore the casts here instead of bellow.

150 ↗

(On Diff #121500)

This will dereference a null pointer (after you initialized this variable above) if the condition above fails.

505 ↗

(On Diff #121500)

Maybe this is an artifact from a missing rebase. I like the original code snippet here better.

828 ↗

(On Diff #121500)

The outermost parens are redundant.

832 ↗

(On Diff #121500)

The outermost parens are redundant.

836 ↗

(On Diff #121500)

Maybe you could rewrite this function as:

return ((Opcode == BO_Or || Opcode == BO_OrAssign) && Value == 0) ||
      ((Opcode == BO_And || Opcode == BO_AndAssign) && ~Value == 0);

882 ↗

(On Diff #121500)

You could move this declaration close to its use.

docs/clang-tidy/checks/misc-redundant-expression.rst

28 ↗

(On Diff #121500)

This is confusing. Maybe it would be better to have two separate example here.

[barancsuk]

Address latest review comments

clang-tidy/misc/RedundantExpressionCheck.cpp

150 ↗

(On Diff #121500)

The entire function ignoreCastsAndCopyConstructorCalls is unnecessary, since when the test cases with operators that take arguments by value were removed. My bad! I eliminated the function.

[xazax.hun]

LGTM! But wait one more reviewer to be sure :)

[aaron.ballman]

clang-tidy/misc/RedundantExpressionCheck.cpp

519 ↗

(On Diff #121744)

Spurious formatting change?

686–687 ↗

(On Diff #121744)

No real need for these locals, is there?

Also, having "ineff-bitwise" along with "ineffective-bitwise" is a bit odd. Can you pick a more clearly distinct name?

[barancsuk]

Address review comments

[aaron.ballman]

LGTM!

[aaron.ballman]

This patch needs to be rebased off trunk before it can be applied cleanly.

[xazax.hun]

In D39285#932013, @aaron.ballman wrote:

This patch needs to be rebased off trunk before it can be applied cleanly.

https://reviews.llvm.org/D39243 is set as a dependency, so I suspect this can be applied cleanly once https://reviews.llvm.org/D39243 landed.

[aaron.ballman]

In D39285#932032, @xazax.hun wrote:

In D39285#932013, @aaron.ballman wrote:

This patch needs to be rebased off trunk before it can be applied cleanly.

https://reviews.llvm.org/D39243 is set as a dependency, so I suspect this can be applied cleanly once https://reviews.llvm.org/D39243 landed.

I have to admit that this stack of interdependent changes makes it *very* hard to effectively review what's going on.

[barancsuk]

:( My initial intention was to simplify the review process by splitting the change-set into small patches, but it seems that this idea fell flat...

[xazax.hun]

In D39285#932815, @barancsuk wrote:

:( My initial intention was to simplify the review process by splitting the change-set into small patches, but it seems that this idea fell flat...

I could not apply the patch after commiting the dependent revision. Could you rebase this on top of tree clang tidy?

[alexfh]

clang-tidy/misc/RedundantExpressionCheck.cpp

871 ↗

(On Diff #123343)

This can be a StringRef to avoid unnecessary copies. Same above.

875 ↗

(On Diff #123343)

I'd use clang diagnostic formatting facilities here to avoid unnecessary temporary strings:

diag(Loc, "expression ... '%0'") << ExprText;

Same above.

[barancsuk]

Address review comments

[xazax.hun]

There was two accepts and the comments found by Alex were resolved, so I went ahead committing this. In case there are further comments, we can address them separately.

clang-tools-extra/trunk/clang-tidy/misc/RedundantExpressionCheck.cpp

 #include "clang/Basic/SourceManager.h"
 #include "clang/Lex/Lexer.h"
 #include "llvm/ADT/APInt.h"
 #include "llvm/ADT/APSInt.h"
 #include "llvm/ADT/FoldingSet.h"
 #include "llvm/Support/Casting.h"
 #include <algorithm>
 #include <cassert>
+#include <cmath>
 #include <cstdint>
 #include <string>
 #include <vector>
 
 using namespace clang::ast_matchers;
 using namespace clang::tidy::matchers;
 
 namespace clang {
if (OpcodeLHS == BO_GT && OpcodeRHS == BO_LT &&
       incrementWithoutOverflow(ValueLHS, ValueLHS_plus1) &&
       APSInt::compareValues(ValueLHS_plus1, ValueRHS) == 0)
     return true;
 
   return false;
 }
 
 // Returns whether the ranges covered by the union of both relational
-// expressions covers the whole domain (i.e. x < 10  and  x > 0).
+// expressions cover the whole domain (i.e. x < 10  and  x > 0).
 static bool rangesFullyCoverDomain(BinaryOperatorKind OpcodeLHS,
                                    const APSInt &ValueLHS,
                                    BinaryOperatorKind OpcodeRHS,
                                    const APSInt &ValueRHS) {
   assert(APSInt::compareValues(ValueLHS, ValueRHS) <= 0 &&
          "Values must be ordered");
 
   // Handle cases where the constants are the same:  x < 5 || x >= 5.
Value = APSInt(32, false);
                  Result.Nodes.getNodeAs<CXXOperatorCallExpr>(OverloadId)) {
     const auto *OverloadedFunctionDecl = dyn_cast_or_null<FunctionDecl>(OverloadedOperatorExpr->getCalleeDecl());
     if (!OverloadedFunctionDecl)
       return false;
 
     if (canOverloadedOperatorArgsBeModified(OverloadedFunctionDecl, false))
       return false;
 
+    if (canOverloadedOperatorArgsBeModified(OverloadedFunctionDecl, false))
+      return false;
+
     if (!OverloadedOperatorExpr->getArg(1)->isIntegerConstantExpr(
             Value, *Result.Context))
       return false;
 
     Symbol = OverloadedOperatorExpr->getArg(0);
     OperandExpr = OverloadedOperatorExpr;
     Opcode = BinaryOperator::getOverloadedOpcode(OverloadedOperatorExpr->getOperator());
 
if ((LhsBinOp->getLHS()->isIntegerConstantExpr(*AstCtx) ||
        LhsBinOp->getRHS()->isIntegerConstantExpr(*AstCtx)) &&
       (RhsBinOp->getLHS()->isIntegerConstantExpr(*AstCtx) ||
        RhsBinOp->getRHS()->isIntegerConstantExpr(*AstCtx)))
     return true;
   return false;
 }
 
 // Retrieves integer constant subexpressions from binary operator expressions
-// that have two equivalent sides
+// that have two equivalent sides.
 // E.g.: from (X == 5) && (X == 5) retrieves 5 and 5.
 static bool retrieveConstExprFromBothSides(const BinaryOperator *&BinOp,
                                            BinaryOperatorKind &MainOpcode,
                                            BinaryOperatorKind &SideOpcode,
                                            const Expr *&LhsConst,
                                            const Expr *&RhsConst,
                                            const ASTContext *AstCtx) {
   assert(areSidesBinaryConstExpressions(BinOp, AstCtx) &&
Finder->addMatcher(
               hasOverloadedOperatorName("&&"), hasOverloadedOperatorName("||"),
               hasOverloadedOperatorName("=")),
           parametersAreEquivalent(),
           // Filter noisy false positives.
           unless(isMacro()), unless(isInTemplateInstantiation()))
           .bind("call"),
       this);
 
+  // Match expressions like: !(1 | 2 | 3)
+  Finder->addMatcher(
+      implicitCastExpr(
+          hasImplicitDestinationType(isInteger()),
+          has(unaryOperator(
+                  hasOperatorName("!"),
+                  hasUnaryOperand(ignoringParenImpCasts(binaryOperator(
+                      anyOf(hasOperatorName("|"), hasOperatorName("&")),
+                      hasLHS(anyOf(binaryOperator(anyOf(hasOperatorName("|"),
+                                                        hasOperatorName("&"))),
+                                   integerLiteral())),
+                      hasRHS(integerLiteral())))))
+                  .bind("logical-bitwise-confusion"))),
+      this);
+
+  // Match expressions like: (X << 8) & 0xFF
+  Finder->addMatcher(
+      binaryOperator(hasOperatorName("&"),
+                     hasEitherOperand(ignoringParenImpCasts(binaryOperator(
+                         hasOperatorName("<<"),
+                         hasRHS(ignoringParenImpCasts(
+                             integerLiteral().bind("shift-const")))))),
+                     hasEitherOperand(ignoringParenImpCasts(
+                         integerLiteral().bind("and-const"))))
+          .bind("left-right-shift-confusion"),
+      this);
+
   // Match common expressions and apply more checks to find redundant
   // sub-expressions.
   //   a) Expr <op> K1 == K2
   //   b) Expr <op> K1 == Expr
   //   c) Expr <op> K1 == Expr <op> K2
   // see: 'checkArithmeticExpr' and 'checkBitwiseExpr'
   const auto BinOpCstLeft = matchBinOpIntegerConstantExpr("lhs");
   const auto BinOpCstRight = matchBinOpIntegerConstantExpr("rhs");
if (LhsOpcode == BO_Add && RhsOpcode == BO_Add) {
                   APSInt::compareValues(LhsValue, RhsValue) == 0)) {
         diag(ComparisonOperator->getOperatorLoc(),
              "logical expression is always false");
       }
     }
   }
 }
 
+static bool exprEvaluatesToZero(BinaryOperatorKind Opcode, APSInt Value) {
+  return (Opcode == BO_And || Opcode == BO_AndAssign) && Value == 0;
+}
+
+static bool exprEvaluatesToBitwiseNegatedZero(BinaryOperatorKind Opcode,
+                                              APSInt Value) {
+  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;
if (const auto *ComparisonOperator = Result.Nodes.getNodeAs<BinaryOperator>(
 
     // Check expression: x | k1 == k2  (i.e. x | 0xFF == 0xF00)
     if (LhsOpcode == BO_Or && (LhsConstant | RhsConstant) != RhsConstant) {
       if (Opcode == BO_EQ)
         diag(Loc, "logical expression is always false");
       else if (Opcode == BO_NE)
         diag(Loc, "logical expression is always true");
     }
+  } else if (const auto *IneffectiveOperator =
+                 Result.Nodes.getNodeAs<BinaryOperator>(
+                     "ineffective-bitwise")) {
+    APSInt Value;
+    const Expr *Sym = nullptr, *ConstExpr = nullptr;
+
+    if (!retrieveSymbolicExpr(Result, "ineffective-bitwise", Sym) ||
+        !retrieveIntegerConstantExpr(Result, "ineffective-bitwise", Value,
+                                     ConstExpr))
+      return;
+
+    if((Value != 0 && ~Value != 0) || Sym->getExprLoc().isMacroID())
+        return;
+
+    SourceLocation Loc = IneffectiveOperator->getOperatorLoc();
+
+    BinaryOperatorKind Opcode = IneffectiveOperator->getOpcode();
+    if (exprEvaluatesToZero(Opcode, Value)) {
+      diag(Loc, "expression always evaluates to 0");
+    } else if (exprEvaluatesToBitwiseNegatedZero(Opcode, Value)) {
+      SourceRange ConstExprRange(ConstExpr->getLocStart(),
+                                 ConstExpr->getLocEnd());
+      StringRef ConstExprText = Lexer::getSourceText(
+          CharSourceRange::getTokenRange(ConstExprRange), *Result.SourceManager,
+          Result.Context->getLangOpts());
+
+      diag(Loc, "expression always evaluates to '%0'") << ConstExprText;
+
+    } else if (exprEvaluatesToSymbolic(Opcode, Value)) {
+      SourceRange SymExprRange(Sym->getLocStart(), Sym->getLocEnd());
+
+      StringRef ExprText = Lexer::getSourceText(
+          CharSourceRange::getTokenRange(SymExprRange), *Result.SourceManager,
+          Result.Context->getLangOpts());
+
+      diag(Loc, "expression always evaluates to '%0'") << ExprText;
+    }
   }
 }
 
 void RedundantExpressionCheck::checkRelationalExpr(
     const MatchFinder::MatchResult &Result) {
   if (const auto *ComparisonOperator = Result.Nodes.getNodeAs<BinaryOperator>(
           "comparisons-of-symbol-and-const")) {
     // Matched expressions are: (x <op> k1) <REL> (x <op> k2).
if (const auto *Call = Result.Nodes.getNodeAs<CXXOperatorCallExpr>("call")) {
 
     if (canOverloadedOperatorArgsBeModified(OverloadedFunctionDecl, true))
       return;
 
     diag(Call->getOperatorLoc(),
          "both sides of overloaded operator are equivalent");
   }
 
+  if (const auto *NegateOperator =
+          Result.Nodes.getNodeAs<UnaryOperator>("logical-bitwise-confusion")) {
+    SourceLocation OperatorLoc = NegateOperator->getOperatorLoc();
+
+    auto Diag =
+        diag(OperatorLoc,
+             "ineffective logical negation operator used; did you mean '~'?");
+    SourceLocation LogicalNotLocation = OperatorLoc.getLocWithOffset(1);
+
+    if (!LogicalNotLocation.isMacroID())
+      Diag << FixItHint::CreateReplacement(
+          CharSourceRange::getCharRange(OperatorLoc, LogicalNotLocation), "~");
+  }
+
+  if (const auto *BinaryAndExpr = Result.Nodes.getNodeAs<BinaryOperator>(
+          "left-right-shift-confusion")) {
+    const auto *ShiftingConst = Result.Nodes.getNodeAs<Expr>("shift-const");
+    assert(ShiftingConst && "Expr* 'ShiftingConst' is nullptr!");
+    APSInt ShiftingValue;
+
+    if (!ShiftingConst->isIntegerConstantExpr(ShiftingValue, *Result.Context))
+      return;
+
+    const auto *AndConst = Result.Nodes.getNodeAs<Expr>("and-const");
+    assert(AndConst && "Expr* 'AndCont' is nullptr!");
+    APSInt AndValue;
+    if (!AndConst->isIntegerConstantExpr(AndValue, *Result.Context))
+      return;
+
+    // If ShiftingConst is shifted left with more bits than the position of the
+    // leftmost 1 in the bit representation of AndValue, AndConstant is
+    // ineffective.
+    if (floor(log2(AndValue.getExtValue())) >= ShiftingValue)
+      return;
+
+    auto Diag = diag(BinaryAndExpr->getOperatorLoc(),
+                     "ineffective bitwise and operation.");
+  }
+
   // Check for the following bound expressions:
   // - "binop-const-compare-to-sym",
   // - "binop-const-compare-to-binop-const",
   // Produced message:
   // -> "logical expression is always false/true"
   checkArithmeticExpr(Result);
 
   // Check for the following bound expression:
   // - "binop-const-compare-to-const",
+  // - "ineffective-bitwise"
   // Produced message:
   // -> "logical expression is always false/true"
+  // -> "expression always evaluates to ..."
   checkBitwiseExpr(Result);
 
   // Check for te following bound expression:
   // - "comparisons-of-symbol-and-const",
   // Produced messages:
   // -> "equivalent expression on both sides of logical operator",
   // -> "logical expression is always false/true"
   // -> "expression is redundant"
   checkRelationalExpr(Result);
 }
 
 } // namespace misc
 } // namespace tidy
 } // namespace clang

clang-tools-extra/trunk/docs/ReleaseNotes.rst

- Added aliases for the `High Integrity C++ Coding Standard <http://www.codingstandard.com/section/index/>`_
   - `hicpp-use-auto <http://clang.llvm.org/extra/clang-tidy/checks/hicpp-use-auto.html>`_
   - `hicpp-use-emplace <http://clang.llvm.org/extra/clang-tidy/checks/hicpp-use-emplace.html>`_
   - `hicpp-use-noexcept <http://clang.llvm.org/extra/clang-tidy/checks/hicpp-use-noexcept.html>`_
   - `hicpp-use-nullptr <http://clang.llvm.org/extra/clang-tidy/checks/hicpp-use-nullptr.html>`_
   - `hicpp-vararg <http://clang.llvm.org/extra/clang-tidy/checks/hicpp-vararg.html>`_
 
 - Added the ability to suppress specific checks (or all checks) in a ``NOLINT`` or ``NOLINTNEXTLINE`` comment.
 
+- Added new functionality to `misc-redundant-expression
+  http://clang.llvm.org/extra/clang-tidy/checks/misc-redundant-expression.html`_ check
+
+  Finds redundant binary operator expressions where the operators are overloaded,
+  and ones that contain the same macros twice.
+  Also checks for assignment expressions that do not change the value of the
+  assigned variable, and expressions that always evaluate to the same value
+  because of possible operator confusion.
+
 Improvements to include-fixer
 -----------------------------
 
 The improvements are...
 
 Improvements to modularize
 --------------------------
 
 The improvements are...

clang-tools-extra/trunk/test/clang-tidy/misc-redundant-expression.cpp

bool TestOverloadedOperator(MyStruct& S) {
   if (S == S) return true;
   // CHECK-MESSAGES: :[[@LINE-1]]:9: warning: both sides of overloaded operator are equivalent
   if (S < S) return true;
   // CHECK-MESSAGES: :[[@LINE-1]]:9: warning: both sides of overloaded operator are equivalent
   if (S != S) return true;
   // CHECK-MESSAGES: :[[@LINE-1]]:9: warning: both sides of overloaded operator are equivalent
   if (S >= S) return true;
   // CHECK-MESSAGES: :[[@LINE-1]]:9: warning: both sides of overloaded operator are equivalent
+
+  return true;
 }
 
 #define LT(x, y) (void)((x) < (y))
 #define COND(x, y, z) ((x)?(y):(z))
 #define EQUALS(x, y) (x) == (y)
 
 int TestMacro(int X, int Y) {
   LT(0, 0);
int TestWithMinMaxInt(int X) {
   if (X + 0x80000000 == X - 0x80000000) return 1;
   // CHECK-MESSAGES: :[[@LINE-1]]:22: warning: logical expression is always true
 
   if (X > 0x7FFFFFFF || X < ((-0x7FFFFFFF)-1)) return 1;
   if (X <= 0x7FFFFFFF && X >= ((-0x7FFFFFFF)-1)) return 1;
 
   return 0;
 }
+
+#define FLAG1 1
+#define FLAG2 2
+#define FLAG3 4
+#define FLAGS (FLAG1 | FLAG2 | FLAG3)
+#define NOTFLAGS !(FLAG1 | FLAG2 | FLAG3)
+int operatorConfusion(int X, int Y, long Z)
+{
+  // Ineffective & expressions.
+  Y = (Y << 8) & 0xff;
+  // CHECK-MESSAGES: :[[@LINE-1]]:16: warning: ineffective bitwise and operation.
+  Y = (Y << 12) & 0xfff;
+  // CHECK-MESSAGES: :[[@LINE-1]]:17: warning: ineffective bitwise and
+  Y = (Y << 12) & 0xff;
+  // CHECK-MESSAGES: :[[@LINE-1]]:17: warning: ineffective bitwise and
+  Y = (Y << 8) & 0x77;
+  // CHECK-MESSAGES: :[[@LINE-1]]:16: warning: ineffective bitwise and
+  Y = (Y << 5) & 0x11;
+  // CHECK-MESSAGES: :[[@LINE-1]]:16: warning: ineffective bitwise and
+
+  // Tests for unmatched types
+  Z = (Z << 8) & 0xff;
+  // CHECK-MESSAGES: :[[@LINE-1]]:16: warning: ineffective bitwise and operation.
+  Y = (Y << 12) & 0xfffL;
+  // CHECK-MESSAGES: :[[@LINE-1]]:17: warning: ineffective bitwise and
+  Z = (Y << 12) & 0xffLL;
+  // CHECK-MESSAGES: :[[@LINE-1]]:17: warning: ineffective bitwise and
+  Y = (Z << 8L) & 0x77L;
+  // CHECK-MESSAGES: :[[@LINE-1]]:17: warning: ineffective bitwise and
+
+  // Effective expressions. Do not check.
+  Y = (Y << 4) & 0x15;
+  Y = (Y << 3) & 0x250;
+  Y = (Y << 9) & 0xF33;
+
+  int K = !(1 | 2 | 4);
+  // CHECK-MESSAGES: :[[@LINE-1]]:11: warning: ineffective logical negation operator used; did you mean '~'?
+  // CHECK-FIXES: {{^}}  int K = ~(1 | 2 | 4);{{$}}
+  K = !(FLAG1 & FLAG2 & FLAG3);
+  // CHECK-MESSAGES: :[[@LINE-1]]:7: warning: ineffective logical negation operator
+  // CHECK-FIXES: {{^}}  K = ~(FLAG1 & FLAG2 & FLAG3);{{$}}
+  K = !(3 | 4);
+  // CHECK-MESSAGES: :[[@LINE-1]]:7: warning: ineffective logical negation operator
+  // CHECK-FIXES: {{^}}  K = ~(3 | 4);{{$}}
+  int NotFlags = !FLAGS;
+  // CHECK-MESSAGES: :[[@LINE-1]]:18: warning: ineffective logical negation operator
+  // CHECK-FIXES: {{^}}  int NotFlags = ~FLAGS;{{$}}
+  NotFlags = NOTFLAGS;
+  // CHECK-MESSAGES: :[[@LINE-1]]:14: warning: ineffective logical negation operator
+  return !(1 | 2 | 4);
+  // CHECK-MESSAGES: :[[@LINE-1]]:10: warning: ineffective logical negation operator
+  // CHECK-FIXES: {{^}}  return ~(1 | 2 | 4);{{$}}
+}
+#undef FLAG1
+#undef FLAG2
+#undef FLAG3