[clang-tidy] New checker for redundant expressions.

[etienneb]

Summary

This checker finds redundant expression on both side of a binary operator.

The current implementation provide a function to check whether expressions
are equivalent. This implementation is able to recognize the common
subset encounter in C++ program. Side-effects like "x++" are not considered
to be equivalent.

There are many False Positives related to macros and to floating point
computations (detecting NaN). The checker is ignoring these cases.

Example:

if( !dst || dst->depth != desired_depth ||
    dst->nChannels != desired_num_channels ||
    dst_size.width != src_size.width ||
    dst_size.height != dst_size.height )    <<--- bug
{

[Eugene.Zelenko]

Please mention this check in docs/ReleaseNotes.rst (in alphabetical order).

Will check catch more complicated cases, like

if ((Point1.x < Point2.x) && (Point1.x < Point2.x)) ?

Will be good idea to add such cases in test.

[etienneb]

In D19451#410014, @Eugene.Zelenko wrote:

Please mention this check in docs/ReleaseNotes.rst (in alphabetical order).

Will check catch more complicated cases, like

if ((Point1.x < Point2.x) && (Point1.x < Point2.x)) ?

It is catching these cases.

Will be good idea to add such cases in test.

I can add it as a test, no prob. I'm never against more tests.

I have more cases implemented, but I prefer landing this piece by piece to let people review it and report false-positive.

I'm able to recognize stuff like:

x == 10 && x <= 12  (x <= 12 is redundant),  and many other cases with bitwise operations.

I need time to deal correctly with False positives. And, I'm not sure it will be part of the same matcher. Will see..

[etienneb]

Will check catch more complicated cases, like

[..]

It is not "yet" catching these cases:

if ((Point2.x > Point1.x) && (Point1.x < Point2.x)) ?

I believe the AreEquivalentExpression should be extended, and probably llifted to utils.
Here again, I propose to do it incrementally.

An other nice extension is to catch cases like:

(x | y | x)

In this case, you need to implement the associative operators.

[etienneb]

addressed eugene requests.

[etienneb]

Tested over LLVM code, no false positives.

Two catches:
http://reviews.llvm.org/D19460
http://reviews.llvm.org/D19451

[alexfh]

Awesome idea!

LG with a couple of nits.

In D19451#410064, @etienneb wrote:

Tested over LLVM code, no false positives.

Two catches:
http://reviews.llvm.org/D19460
http://reviews.llvm.org/D19451

The second link refers to this revision ;)

clang-tidy/misc/RedundantExpressionCheck.cpp

22

This is to some degree similar to comparing llvm::FoldingSetNodeIDs created using Stmt::Profile. However it's only useful to check for identical expressions and won't work, if you're going to extend this to equivalent expressions.

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

11

Please enclose true and false in backquotes.

[alexfh]

BTW, have you seen the alpha.core.IdenticalExpr static analyzer checker?

[alexfh]

In D19451#411990, @alexfh wrote:

BTW, have you seen the alpha.core.IdenticalExpr static analyzer checker?

Anna, Jordan, and whoever else is interested in the alpha.core.IdenticalExpr checker (lib/StaticAnalyzer/Checkers/IdenticalExprChecker.cpp), it looks like Etienne has reinvented a large part of this checker as a clang-tidy check. I'm not sure which of these supports more cases and has more false positives (given that the alpha.core.IdenticalExpr checker was there for quite a while, but IIUC, this clang-tidy check has been tested on a huge code base with pretty good results).

A few questions to all of you:

1. is the alpha.core.IdenticalExpr checker going to be released in the near future?
2. is anyone actively working on it?
3. given that Etienne seems to be planning to continue actively working on the clang-tidy analog of that static analyzer checker, are you fine to move all of this checker's (alpha.core.IdenticalExpr) functionality to clang-tidy?
4. more generally, should we officially recommend to use clang-tidy (instead of the static analyzer) for writing AST-based checks that don't require any path-based analysis?

[etienneb]

In D19451#412017, @alexfh wrote:

In D19451#411990, @alexfh wrote:

BTW, have you seen the alpha.core.IdenticalExpr static analyzer checker?

Anna, Jordan, and whoever else is interested in the alpha.core.IdenticalExpr checker (lib/StaticAnalyzer/Checkers/IdenticalExprChecker.cpp), it looks like Etienne has reinvented a large part of this checker as a clang-tidy check. I'm not sure which of these supports more cases and has more false positives (given that the alpha.core.IdenticalExpr checker was there for quite a while, but IIUC, this clang-tidy check has been tested on a huge code base with pretty good results).

BTW, have you seen the alpha.core.IdenticalExpr static analyzer checker?

Yes, I looked at it. The AreEquivalentExpression is pretty much a variant of that code (a simplification).

A few questions to all of you:

1. is the alpha.core.IdenticalExpr checker going to be released in the near future?
2. is anyone actively working on it?
3. given that Etienne seems to be planning to continue actively working on the clang-tidy analog of that static analyzer checker, are you fine to move all of this checker's (alpha.core.IdenticalExpr) functionality to clang-tidy?
4. more generally, should we officially recommend to use clang-tidy (instead of the static analyzer) for writing AST-based checks that don't require any path-based analysis?

For now, there are overlap between both checkers. I think 'alpha.core.IdenticalExpr' is in "alpha"-mode because there are too many false-positives related to cases like macro/floating-points (detecting NaN,...). The current checker has a pretty-low false-positive ratio. But, some redundant expressions won't be reported.

i.e.   A[(3) - (3)]  which is frequent in bison-generated files won't be reported.

On a long term, I'm planning rules to enhance matching redundant expressions like:

x == 10 && x < 12   (x < 12 is useless)

[etienneb]

address alexfh comments.

clang-tidy/misc/RedundantExpressionCheck.cpp

22

Exact. There is plan to extend the notion of "equivalent".
I think we should lift this to "utils", and maybe we can also provide a "isIdenticalExpression" based on FoldingSet.

clang-tidy/misc/CMakeLists.txt

add_clang_library(clangTidyMiscModule
   MisplacedWideningCastCheck.cpp
   MoveConstantArgumentCheck.cpp
   MoveConstructorInitCheck.cpp
   MultipleStatementMacroCheck.cpp
   NewDeleteOverloadsCheck.cpp
   NoexceptMoveConstructorCheck.cpp
   NonCopyableObjects.cpp
   PointerAndIntegralOperationCheck.cpp
+  RedundantExpressionCheck.cpp
   SizeofContainerCheck.cpp
   SizeofExpressionCheck.cpp
   StaticAssertCheck.cpp
   StringConstructorCheck.cpp
   StringIntegerAssignmentCheck.cpp
   StringLiteralWithEmbeddedNulCheck.cpp
   SuspiciousMissingCommaCheck.cpp
   SuspiciousSemicolonCheck.cpp

clang-tidy/misc/MiscTidyModule.cpp

 #include "MisplacedWideningCastCheck.h"
 #include "MoveConstantArgumentCheck.h"
 #include "MoveConstructorInitCheck.h"
 #include "MultipleStatementMacroCheck.h"
 #include "NewDeleteOverloadsCheck.h"
 #include "NoexceptMoveConstructorCheck.h"
 #include "NonCopyableObjects.h"
 #include "PointerAndIntegralOperationCheck.h"
+#include "RedundantExpressionCheck.h"
 #include "SizeofContainerCheck.h"
 #include "SizeofExpressionCheck.h"
 #include "StaticAssertCheck.h"
 #include "StringConstructorCheck.h"
 #include "StringIntegerAssignmentCheck.h"
 #include "StringLiteralWithEmbeddedNulCheck.h"
 #include "SuspiciousMissingCommaCheck.h"
 #include "SuspiciousSemicolonCheck.h"
void addCheckFactories(ClangTidyCheckFactories &CheckFactories) override {
     CheckFactories.registerCheck<NewDeleteOverloadsCheck>(
         "misc-new-delete-overloads");
     CheckFactories.registerCheck<NoexceptMoveConstructorCheck>(
         "misc-noexcept-move-constructor");
     CheckFactories.registerCheck<NonCopyableObjectsCheck>(
         "misc-non-copyable-objects");
     CheckFactories.registerCheck<PointerAndIntegralOperationCheck>(
         "misc-pointer-and-integral-operation");
+    CheckFactories.registerCheck<RedundantExpressionCheck>(
+        "misc-redundant-expression");
     CheckFactories.registerCheck<SizeofContainerCheck>("misc-sizeof-container");
     CheckFactories.registerCheck<SizeofExpressionCheck>(
         "misc-sizeof-expression");
     CheckFactories.registerCheck<StaticAssertCheck>(
         "misc-static-assert");
     CheckFactories.registerCheck<StringConstructorCheck>(
         "misc-string-constructor");
     CheckFactories.registerCheck<StringIntegerAssignmentCheck>(

clang-tidy/misc/RedundantExpressionCheck.h

+//===--- RedundantExpressionCheck.h - clang-tidy-----------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_MISC_REDUNDANT_EXPRESSION_H
+#define LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_MISC_REDUNDANT_EXPRESSION_H
+
+#include "../ClangTidy.h"
+
+namespace clang {
+namespace tidy {
+namespace misc {
+
+/// Detect useless or suspicious redundant expressions.
+///
+/// For the user-facing documentation see:
+/// http://clang.llvm.org/extra/clang-tidy/checks/misc-redundant-expression.html
+class RedundantExpressionCheck : public ClangTidyCheck {
+public:
+  RedundantExpressionCheck(StringRef Name, ClangTidyContext *Context)
+      : ClangTidyCheck(Name, Context) {}
+  void registerMatchers(ast_matchers::MatchFinder *Finder) override;
+  void check(const ast_matchers::MatchFinder::MatchResult &Result) override;
+};
+
+} // namespace misc
+} // namespace tidy
+} // namespace clang
+
+#endif // LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_MISC_REDUNDANT_EXPRESSION_H

clang-tidy/misc/RedundantExpressionCheck.cpp

+//===--- RedundantExpressionCheck.cpp - clang-tidy-------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "RedundantExpressionCheck.h"
+#include "../utils/Matchers.h"
+#include "clang/AST/ASTContext.h"
+#include "clang/ASTMatchers/ASTMatchFinder.h"
+
+using namespace clang::ast_matchers;
+
+namespace clang {
+namespace tidy {
+namespace misc {
+
+static bool AreIdenticalExpr(const Expr *Left, const Expr *Right) {
+  if (!Left || !Right)
+    return !Left && !Right;
+
+  Left = Left->IgnoreParens();
+  Right = Right->IgnoreParens();
+
+  // Compare classes.
+  if (Left->getStmtClass() != Right->getStmtClass())
+    return false;
+
+  // Compare children.
+  Expr::const_child_iterator LeftIter = Left->child_begin();
+  Expr::const_child_iterator RightIter = Right->child_begin();
+  while (LeftIter != Left->child_end() && RightIter != Right->child_end()) {
+    if (!AreIdenticalExpr(dyn_cast<Expr>(*LeftIter),
+                          dyn_cast<Expr>(*RightIter)))
+      return false;
+    ++LeftIter;
+    ++RightIter;
+  }
+  if (LeftIter != Left->child_end() || RightIter != Right->child_end())
+    return false;
+
+  // Perform extra checks.
+  switch (Left->getStmtClass()) {
+  default:
+    return false;
+
+  case Stmt::CharacterLiteralClass:
+    return cast<CharacterLiteral>(Left)->getValue() ==
+           cast<CharacterLiteral>(Right)->getValue();
+  case Stmt::IntegerLiteralClass: {
+    llvm::APInt LeftLit = cast<IntegerLiteral>(Left)->getValue();
+    llvm::APInt RightLit = cast<IntegerLiteral>(Right)->getValue();
+    return LeftLit.getBitWidth() == RightLit.getBitWidth() && LeftLit == RightLit;
+  }
+  case Stmt::FloatingLiteralClass:
+    return cast<FloatingLiteral>(Left)->getValue().bitwiseIsEqual(
+        cast<FloatingLiteral>(Right)->getValue());
+  case Stmt::StringLiteralClass:
+    return cast<StringLiteral>(Left)->getBytes() ==
+           cast<StringLiteral>(Right)->getBytes();
+
+  case Stmt::DeclRefExprClass:
+    return cast<DeclRefExpr>(Left)->getDecl() ==
+           cast<DeclRefExpr>(Right)->getDecl();
+  case Stmt::MemberExprClass:
+    return cast<MemberExpr>(Left)->getMemberDecl() ==
+           cast<MemberExpr>(Right)->getMemberDecl();
+
+  case Stmt::CStyleCastExprClass:
+    return cast<CStyleCastExpr>(Left)->getTypeAsWritten() ==
+           cast<CStyleCastExpr>(Right)->getTypeAsWritten();
+
+  case Stmt::CallExprClass:
+  case Stmt::ImplicitCastExprClass:
+  case Stmt::ArraySubscriptExprClass:
+    return true;
+
+  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();
+  }
+}
+
+AST_MATCHER(BinaryOperator, OperandsAreEquivalent) {
+  return AreIdenticalExpr(Node.getLHS(), Node.getRHS());
+}
+
+AST_MATCHER(BinaryOperator, isInMacro) {
+  return Node.getOperatorLoc().isMacroID();
+}
+
+AST_MATCHER(Expr, isInstantiationDependent) {
+  return Node.isInstantiationDependent();
+}
+
+void RedundantExpressionCheck::registerMatchers(MatchFinder *Finder) {
+  const auto AnyLiteralExpr = ignoringParenImpCasts(
+      anyOf(cxxBoolLiteral(), characterLiteral(), integerLiteral()));
+
+  Finder->addMatcher(
+      binaryOperator(anyOf(hasOperatorName("-"), hasOperatorName("/"),
+                           hasOperatorName("%"), hasOperatorName("|"),
+                           hasOperatorName("&"), hasOperatorName("^"),
+                           matchers::isComparisonOperator(),
+                           hasOperatorName("&&"), hasOperatorName("||"),
+                           hasOperatorName("=")),
+                     OperandsAreEquivalent(),
+                     // Filter noisy false positives.
+                     unless(isInstantiationDependent()),
+                     unless(isInMacro()),
+                     unless(hasType(realFloatingPointType())),
+                     unless(hasEitherOperand(hasType(realFloatingPointType()))),
+                     unless(hasLHS(AnyLiteralExpr)))
+          .bind("binary"),
+      this);
+}
+
+void RedundantExpressionCheck::check(const MatchFinder::MatchResult &Result) {
+  if (const auto *BinOp = Result.Nodes.getNodeAs<BinaryOperator>("binary"))
+    diag(BinOp->getOperatorLoc(), "both side of operator are equivalent");
+}
+
+} // namespace misc
+} // namespace tidy
+} // namespace clang

docs/ReleaseNotes.rst

- New `misc-multiple-statement-macro
 
   Detect multiple statement macros that are used in unbraced conditionals.
 
 - New `misc-pointer-and-integral-operation
   <http://clang.llvm.org/extra/clang-tidy/checks/misc-pointer-and-integral-operation.html>`_ check
 
   Warns about suspicious operations involving pointers and integral types.
 
+- New `misc-redundant-expression
+  <http://clang.llvm.org/extra/clang-tidy/checks/misc-redundant-expression.html>`_ check
+
+  Warns about redundant and equivalent expressions.
+
 - New `misc-sizeof-expression
   <http://clang.llvm.org/extra/clang-tidy/checks/misc-sizeof-expression.html>`_ check
 
   Warns about incorrect uses of ``sizeof`` operator.
 
 - New `misc-string-constructor
   <http://clang.llvm.org/extra/clang-tidy/checks/misc-string-constructor.html>`_ check
 

docs/clang-tidy/checks/list.rst

.. toctree::
    misc-macro-repeated-side-effects
    misc-misplaced-widening-cast
    misc-move-constructor-init
    misc-multiple-statement-macro
    misc-new-delete-overloads
    misc-noexcept-move-constructor
    misc-non-copyable-objects
    misc-pointer-and-integral-operation
+   misc-redundant-expression
    misc-sizeof-container
    misc-sizeof-expression
    misc-static-assert
    misc-string-constructor
    misc-string-integer-assignment
    misc-string-literal-with-embedded-nul
    misc-suspicious-missing-comma
    misc-suspicious-semicolon

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

+.. title:: clang-tidy - misc-redundant-expression
+
+misc-redundant-expression
+=========================
+
+Detect redundant expressions which are typically errors due to copy-paste.
+
+Depending on the operator expressions may be
+  * redundant,
+  * always be `true`,
+  * always be `false`,
+  * always be a constant (zero or one)
+
+Example:
+.. code:: c++
+
+  ((x+1) | (x+1))             // (x+1) is redundant
+  (p->x == p->x)              // always true
+  (p->x < p->x)               // always false
+  (speed - speed + 1 == 12)   // speed - speed is always zero

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

+// RUN: %check_clang_tidy %s misc-redundant-expression %t
+
+struct Point {
+  int x;
+  int y;
+  int a[5];
+} P;
+
+extern Point P1;
+extern Point P2;
+
+extern int foo(int x);
+extern int bar(int x);
+extern int bat(int x, int y);
+
+int Test(int X, int Y) {
+  if (X - X) return 1;
+  // CHECK-MESSAGES: :[[@LINE-1]]:9: warning: both side of operator are equivalent [misc-redundant-expression]
+  if (X / X) return 1;
+  // CHECK-MESSAGES: :[[@LINE-1]]:9: warning: both side of operator are equivalent
+  if (X % X) return 1;
+  // CHECK-MESSAGES: :[[@LINE-1]]:9: warning: both side of operator are equivalent
+
+  if (X & X) return 1;
+  // CHECK-MESSAGES: :[[@LINE-1]]:9: warning: both side of operator are equivalent
+  if (X | X) return 1;
+  // CHECK-MESSAGES: :[[@LINE-1]]:9: warning: both side of operator are equivalent
+  if (X ^ X) return 1;
+  // CHECK-MESSAGES: :[[@LINE-1]]:9: warning: both side of operator are equivalent
+
+  if (X < X) return 1;
+  // CHECK-MESSAGES: :[[@LINE-1]]:9: warning: both side of operator are equivalent
+  if (X <= X) return 1;
+  // CHECK-MESSAGES: :[[@LINE-1]]:9: warning: both side of operator are equivalent
+  if (X > X) return 1;
+  // CHECK-MESSAGES: :[[@LINE-1]]:9: warning: both side of operator are equivalent
+  if (X >= X) return 1;
+  // CHECK-MESSAGES: :[[@LINE-1]]:9: warning: both side of operator are equivalent
+
+  if (X && X) return 1;
+  // CHECK-MESSAGES: :[[@LINE-1]]:9: warning: both side of operator are equivalent
+  if (X || X) return 1;
+  // CHECK-MESSAGES: :[[@LINE-1]]:9: warning: both side of operator are equivalent
+
+  if (X != (((X)))) return 1;
+  // CHECK-MESSAGES: :[[@LINE-1]]:9: warning: both side of operator are equivalent
+
+  if (X + 1 == X + 1) return 1;
+  // CHECK-MESSAGES: :[[@LINE-1]]:13: warning: both side of operator are equivalent
+  if (X + 1 != X + 1) return 1;
+  // CHECK-MESSAGES: :[[@LINE-1]]:13: warning: both side of operator are equivalent
+  if (X + 1 <= X + 1) return 1;
+  // CHECK-MESSAGES: :[[@LINE-1]]:13: warning: both side of operator are equivalent
+  if (X + 1 >= X + 1) return 1;
+  // CHECK-MESSAGES: :[[@LINE-1]]:13: warning: both side of operator are equivalent
+
+  if ((X != 1 || Y != 1) && (X != 1 || Y != 1)) return 1;
+  // CHECK-MESSAGES: :[[@LINE-1]]:26: warning: both side of operator are equivalent
+  if (P.a[X - P.x] != P.a[X - P.x]) return 1;
+  // CHECK-MESSAGES: :[[@LINE-1]]:20: warning: both side of operator are equivalent
+
+  if ((int)X < (int)X) return 1;
+  // CHECK-MESSAGES: :[[@LINE-1]]:14: warning: both side of operator are equivalent
+
+  if ( + "dummy" == + "dummy") return 1;
+  // CHECK-MESSAGES: :[[@LINE-1]]:18: warning: both side of operator are equivalent
+  if (L"abc" == L"abc") return 1;     
+  // CHECK-MESSAGES: :[[@LINE-1]]:14: warning: both side of operator are equivalent
+
+  if (foo(0) - 2 < foo(0) - 2) return 1;
+  // CHECK-MESSAGES: :[[@LINE-1]]:18: warning: both side of operator are equivalent  
+  if (foo(bar(0)) < (foo(bar((0))))) return 1;
+  // CHECK-MESSAGES: :[[@LINE-1]]:19: warning: both side of operator are equivalent  
+
+  if (P1.x < P2.x && P1.x < P2.x) return 1;
+  // CHECK-MESSAGES: :[[@LINE-1]]:19: warning: both side of operator are equivalent  
+  if (P2.a[P1.x + 2] < P2.x && P2.a[(P1.x) + (2)] < (P2.x)) return 1;
+  // CHECK-MESSAGES: :[[@LINE-1]]:29: warning: both side of operator are equivalent  
+
+  return 0;
+}
+
+int Valid(int X, int Y) {
+  if (X != Y) return 1;
+  if (X == X + 0) return 1;
+  if (P.x == P.y) return 1;
+  if (P.a[P.x] < P.a[P.y]) return 1;
+  if (P.a[0] < P.a[1]) return 1;
+
+  if (P.a[0] < P.a[0ULL]) return 1;
+  if (0 < 0ULL) return 1;
+  if ((int)0 < (int)0ULL) return 1;
+
+  if (++X != ++X) return 1;
+  if (P.a[X]++ != P.a[X]++) return 1;
+  if (P.a[X++] != P.a[X++]) return 1;
+
+  if ("abc" == "ABC") return 1;
+  if (foo(bar(0)) < (foo(bat(0, 1)))) return 1;
+  return 0;
+}
+
+#define LT(x, y) (void)((x) < (y))
+
+int TestMacro(int X, int Y) {
+  LT(0, 0);
+  LT(1, 0);
+  LT(X, X);
+  LT(X+1, X + 1);
+}
+
+int TestFalsePositive(int* A, int X, float F) {
+  // Produced by bison.
+  X = A[(2) - (2)];
+  X = A['a' - 'a'];
+
+  // Testing NaN.
+  if (F != F && F == F) return 1;
+  return 0;
+}