clang-tools  15.0.0git
RedundantExpressionCheck.cpp
Go to the documentation of this file.
1 //===--- RedundantExpressionCheck.cpp - clang-tidy-------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 
10 #include "../utils/Matchers.h"
11 #include "../utils/OptionsUtils.h"
12 #include "clang/AST/ASTContext.h"
13 #include "clang/ASTMatchers/ASTMatchFinder.h"
14 #include "clang/Basic/LLVM.h"
15 #include "clang/Basic/SourceLocation.h"
16 #include "clang/Basic/SourceManager.h"
17 #include "clang/Lex/Lexer.h"
18 #include "llvm/ADT/APInt.h"
19 #include "llvm/ADT/APSInt.h"
20 #include "llvm/ADT/FoldingSet.h"
21 #include "llvm/ADT/SmallBitVector.h"
22 #include "llvm/Support/Casting.h"
23 #include "llvm/Support/FormatVariadic.h"
24 #include <algorithm>
25 #include <cassert>
26 #include <cstdint>
27 #include <string>
28 #include <vector>
29 
30 using namespace clang::ast_matchers;
31 using namespace clang::tidy::matchers;
32 
33 namespace clang {
34 namespace tidy {
35 namespace misc {
36 namespace {
37 using llvm::APSInt;
38 
39 static constexpr llvm::StringLiteral KnownBannedMacroNames[] = {
40  "EAGAIN",
41  "EWOULDBLOCK",
42  "SIGCLD",
43  "SIGCHLD",
44 };
45 
46 static bool incrementWithoutOverflow(const APSInt &Value, APSInt &Result) {
47  Result = Value;
48  ++Result;
49  return Value < Result;
50 }
51 
52 static bool areEquivalentNameSpecifier(const NestedNameSpecifier *Left,
53  const NestedNameSpecifier *Right) {
54  llvm::FoldingSetNodeID LeftID, RightID;
55  Left->Profile(LeftID);
56  Right->Profile(RightID);
57  return LeftID == RightID;
58 }
59 
60 static bool areEquivalentExpr(const Expr *Left, const Expr *Right) {
61  if (!Left || !Right)
62  return !Left && !Right;
63 
64  Left = Left->IgnoreParens();
65  Right = Right->IgnoreParens();
66 
67  // Compare classes.
68  if (Left->getStmtClass() != Right->getStmtClass())
69  return false;
70 
71  // Compare children.
72  Expr::const_child_iterator LeftIter = Left->child_begin();
73  Expr::const_child_iterator RightIter = Right->child_begin();
74  while (LeftIter != Left->child_end() && RightIter != Right->child_end()) {
75  if (!areEquivalentExpr(dyn_cast_or_null<Expr>(*LeftIter),
76  dyn_cast_or_null<Expr>(*RightIter)))
77  return false;
78  ++LeftIter;
79  ++RightIter;
80  }
81  if (LeftIter != Left->child_end() || RightIter != Right->child_end())
82  return false;
83 
84  // Perform extra checks.
85  switch (Left->getStmtClass()) {
86  default:
87  return false;
88 
89  case Stmt::CharacterLiteralClass:
90  return cast<CharacterLiteral>(Left)->getValue() ==
91  cast<CharacterLiteral>(Right)->getValue();
92  case Stmt::IntegerLiteralClass: {
93  llvm::APInt LeftLit = cast<IntegerLiteral>(Left)->getValue();
94  llvm::APInt RightLit = cast<IntegerLiteral>(Right)->getValue();
95  return LeftLit.getBitWidth() == RightLit.getBitWidth() &&
96  LeftLit == RightLit;
97  }
98  case Stmt::FloatingLiteralClass:
99  return cast<FloatingLiteral>(Left)->getValue().bitwiseIsEqual(
100  cast<FloatingLiteral>(Right)->getValue());
101  case Stmt::StringLiteralClass:
102  return cast<StringLiteral>(Left)->getBytes() ==
103  cast<StringLiteral>(Right)->getBytes();
104  case Stmt::CXXOperatorCallExprClass:
105  return cast<CXXOperatorCallExpr>(Left)->getOperator() ==
106  cast<CXXOperatorCallExpr>(Right)->getOperator();
107  case Stmt::DependentScopeDeclRefExprClass:
108  if (cast<DependentScopeDeclRefExpr>(Left)->getDeclName() !=
109  cast<DependentScopeDeclRefExpr>(Right)->getDeclName())
110  return false;
111  return areEquivalentNameSpecifier(
112  cast<DependentScopeDeclRefExpr>(Left)->getQualifier(),
113  cast<DependentScopeDeclRefExpr>(Right)->getQualifier());
114  case Stmt::DeclRefExprClass:
115  return cast<DeclRefExpr>(Left)->getDecl() ==
116  cast<DeclRefExpr>(Right)->getDecl();
117  case Stmt::MemberExprClass:
118  return cast<MemberExpr>(Left)->getMemberDecl() ==
119  cast<MemberExpr>(Right)->getMemberDecl();
120  case Stmt::CXXFoldExprClass:
121  return cast<CXXFoldExpr>(Left)->getOperator() ==
122  cast<CXXFoldExpr>(Right)->getOperator();
123  case Stmt::CXXFunctionalCastExprClass:
124  case Stmt::CStyleCastExprClass:
125  return cast<ExplicitCastExpr>(Left)->getTypeAsWritten() ==
126  cast<ExplicitCastExpr>(Right)->getTypeAsWritten();
127  case Stmt::CallExprClass:
128  case Stmt::ImplicitCastExprClass:
129  case Stmt::ArraySubscriptExprClass:
130  return true;
131  case Stmt::UnaryOperatorClass:
132  if (cast<UnaryOperator>(Left)->isIncrementDecrementOp())
133  return false;
134  return cast<UnaryOperator>(Left)->getOpcode() ==
135  cast<UnaryOperator>(Right)->getOpcode();
136  case Stmt::BinaryOperatorClass:
137  if (cast<BinaryOperator>(Left)->isAssignmentOp())
138  return false;
139  return cast<BinaryOperator>(Left)->getOpcode() ==
140  cast<BinaryOperator>(Right)->getOpcode();
141  case Stmt::UnaryExprOrTypeTraitExprClass:
142  const auto *LeftUnaryExpr =
143  cast<UnaryExprOrTypeTraitExpr>(Left);
144  const auto *RightUnaryExpr =
145  cast<UnaryExprOrTypeTraitExpr>(Right);
146  if (LeftUnaryExpr->isArgumentType() && RightUnaryExpr->isArgumentType())
147  return LeftUnaryExpr->getArgumentType() ==
148  RightUnaryExpr->getArgumentType();
149  if (!LeftUnaryExpr->isArgumentType() && !RightUnaryExpr->isArgumentType())
150  return areEquivalentExpr(LeftUnaryExpr->getArgumentExpr(),
151  RightUnaryExpr->getArgumentExpr());
152 
153  return false;
154  }
155 }
156 
157 // For a given expression 'x', returns whether the ranges covered by the
158 // relational operators are equivalent (i.e. x <= 4 is equivalent to x < 5).
159 static bool areEquivalentRanges(BinaryOperatorKind OpcodeLHS,
160  const APSInt &ValueLHS,
161  BinaryOperatorKind OpcodeRHS,
162  const APSInt &ValueRHS) {
163  assert(APSInt::compareValues(ValueLHS, ValueRHS) <= 0 &&
164  "Values must be ordered");
165  // Handle the case where constants are the same: x <= 4 <==> x <= 4.
166  if (APSInt::compareValues(ValueLHS, ValueRHS) == 0)
167  return OpcodeLHS == OpcodeRHS;
168 
169  // Handle the case where constants are off by one: x <= 4 <==> x < 5.
170  APSInt ValueLhsPlus1;
171  return ((OpcodeLHS == BO_LE && OpcodeRHS == BO_LT) ||
172  (OpcodeLHS == BO_GT && OpcodeRHS == BO_GE)) &&
173  incrementWithoutOverflow(ValueLHS, ValueLhsPlus1) &&
174  APSInt::compareValues(ValueLhsPlus1, ValueRHS) == 0;
175 }
176 
177 // For a given expression 'x', returns whether the ranges covered by the
178 // relational operators are fully disjoint (i.e. x < 4 and x > 7).
179 static bool areExclusiveRanges(BinaryOperatorKind OpcodeLHS,
180  const APSInt &ValueLHS,
181  BinaryOperatorKind OpcodeRHS,
182  const APSInt &ValueRHS) {
183  assert(APSInt::compareValues(ValueLHS, ValueRHS) <= 0 &&
184  "Values must be ordered");
185 
186  // Handle cases where the constants are the same.
187  if (APSInt::compareValues(ValueLHS, ValueRHS) == 0) {
188  switch (OpcodeLHS) {
189  case BO_EQ:
190  return OpcodeRHS == BO_NE || OpcodeRHS == BO_GT || OpcodeRHS == BO_LT;
191  case BO_NE:
192  return OpcodeRHS == BO_EQ;
193  case BO_LE:
194  return OpcodeRHS == BO_GT;
195  case BO_GE:
196  return OpcodeRHS == BO_LT;
197  case BO_LT:
198  return OpcodeRHS == BO_EQ || OpcodeRHS == BO_GT || OpcodeRHS == BO_GE;
199  case BO_GT:
200  return OpcodeRHS == BO_EQ || OpcodeRHS == BO_LT || OpcodeRHS == BO_LE;
201  default:
202  return false;
203  }
204  }
205 
206  // Handle cases where the constants are different.
207  if ((OpcodeLHS == BO_EQ || OpcodeLHS == BO_LT || OpcodeLHS == BO_LE) &&
208  (OpcodeRHS == BO_EQ || OpcodeRHS == BO_GT || OpcodeRHS == BO_GE))
209  return true;
210 
211  // Handle the case where constants are off by one: x > 5 && x < 6.
212  APSInt ValueLhsPlus1;
213  if (OpcodeLHS == BO_GT && OpcodeRHS == BO_LT &&
214  incrementWithoutOverflow(ValueLHS, ValueLhsPlus1) &&
215  APSInt::compareValues(ValueLhsPlus1, ValueRHS) == 0)
216  return true;
217 
218  return false;
219 }
220 
221 // Returns whether the ranges covered by the union of both relational
222 // expressions cover the whole domain (i.e. x < 10 and x > 0).
223 static bool rangesFullyCoverDomain(BinaryOperatorKind OpcodeLHS,
224  const APSInt &ValueLHS,
225  BinaryOperatorKind OpcodeRHS,
226  const APSInt &ValueRHS) {
227  assert(APSInt::compareValues(ValueLHS, ValueRHS) <= 0 &&
228  "Values must be ordered");
229 
230  // Handle cases where the constants are the same: x < 5 || x >= 5.
231  if (APSInt::compareValues(ValueLHS, ValueRHS) == 0) {
232  switch (OpcodeLHS) {
233  case BO_EQ:
234  return OpcodeRHS == BO_NE;
235  case BO_NE:
236  return OpcodeRHS == BO_EQ;
237  case BO_LE:
238  return OpcodeRHS == BO_GT || OpcodeRHS == BO_GE;
239  case BO_LT:
240  return OpcodeRHS == BO_GE;
241  case BO_GE:
242  return OpcodeRHS == BO_LT || OpcodeRHS == BO_LE;
243  case BO_GT:
244  return OpcodeRHS == BO_LE;
245  default:
246  return false;
247  }
248  }
249 
250  // Handle the case where constants are off by one: x <= 4 || x >= 5.
251  APSInt ValueLhsPlus1;
252  if (OpcodeLHS == BO_LE && OpcodeRHS == BO_GE &&
253  incrementWithoutOverflow(ValueLHS, ValueLhsPlus1) &&
254  APSInt::compareValues(ValueLhsPlus1, ValueRHS) == 0)
255  return true;
256 
257  // Handle cases where the constants are different: x > 4 || x <= 7.
258  if ((OpcodeLHS == BO_GT || OpcodeLHS == BO_GE) &&
259  (OpcodeRHS == BO_LT || OpcodeRHS == BO_LE))
260  return true;
261 
262  // Handle cases where constants are different but both ops are !=, like:
263  // x != 5 || x != 10
264  if (OpcodeLHS == BO_NE && OpcodeRHS == BO_NE)
265  return true;
266 
267  return false;
268 }
269 
270 static bool rangeSubsumesRange(BinaryOperatorKind OpcodeLHS,
271  const APSInt &ValueLHS,
272  BinaryOperatorKind OpcodeRHS,
273  const APSInt &ValueRHS) {
274  int Comparison = APSInt::compareValues(ValueLHS, ValueRHS);
275  switch (OpcodeLHS) {
276  case BO_EQ:
277  return OpcodeRHS == BO_EQ && Comparison == 0;
278  case BO_NE:
279  return (OpcodeRHS == BO_NE && Comparison == 0) ||
280  (OpcodeRHS == BO_EQ && Comparison != 0) ||
281  (OpcodeRHS == BO_LT && Comparison >= 0) ||
282  (OpcodeRHS == BO_LE && Comparison > 0) ||
283  (OpcodeRHS == BO_GT && Comparison <= 0) ||
284  (OpcodeRHS == BO_GE && Comparison < 0);
285 
286  case BO_LT:
287  return ((OpcodeRHS == BO_LT && Comparison >= 0) ||
288  (OpcodeRHS == BO_LE && Comparison > 0) ||
289  (OpcodeRHS == BO_EQ && Comparison > 0));
290  case BO_GT:
291  return ((OpcodeRHS == BO_GT && Comparison <= 0) ||
292  (OpcodeRHS == BO_GE && Comparison < 0) ||
293  (OpcodeRHS == BO_EQ && Comparison < 0));
294  case BO_LE:
295  return (OpcodeRHS == BO_LT || OpcodeRHS == BO_LE || OpcodeRHS == BO_EQ) &&
296  Comparison >= 0;
297  case BO_GE:
298  return (OpcodeRHS == BO_GT || OpcodeRHS == BO_GE || OpcodeRHS == BO_EQ) &&
299  Comparison <= 0;
300  default:
301  return false;
302  }
303 }
304 
305 static void transformSubToCanonicalAddExpr(BinaryOperatorKind &Opcode,
306  APSInt &Value) {
307  if (Opcode == BO_Sub) {
308  Opcode = BO_Add;
309  Value = -Value;
310  }
311 }
312 
313 // to use in the template below
314 static OverloadedOperatorKind getOp(const BinaryOperator *Op) {
315  return BinaryOperator::getOverloadedOperator(Op->getOpcode());
316 }
317 
318 static OverloadedOperatorKind getOp(const CXXOperatorCallExpr *Op) {
319  if (Op->getNumArgs() != 2)
320  return OO_None;
321  return Op->getOperator();
322 }
323 
324 static std::pair<const Expr *, const Expr *>
325 getOperands(const BinaryOperator *Op) {
326  return {Op->getLHS()->IgnoreParenImpCasts(),
327  Op->getRHS()->IgnoreParenImpCasts()};
328 }
329 
330 static std::pair<const Expr *, const Expr *>
331 getOperands(const CXXOperatorCallExpr *Op) {
332  return {Op->getArg(0)->IgnoreParenImpCasts(),
333  Op->getArg(1)->IgnoreParenImpCasts()};
334 }
335 
336 template <typename TExpr>
337 static const TExpr *checkOpKind(const Expr *TheExpr,
338  OverloadedOperatorKind OpKind) {
339  const auto *AsTExpr = dyn_cast_or_null<TExpr>(TheExpr);
340  if (AsTExpr && getOp(AsTExpr) == OpKind)
341  return AsTExpr;
342 
343  return nullptr;
344 }
345 
346 // returns true if a subexpression has two directly equivalent operands and
347 // is already handled by operands/parametersAreEquivalent
348 template <typename TExpr, unsigned N>
349 static bool collectOperands(const Expr *Part,
350  SmallVector<const Expr *, N> &AllOperands,
351  OverloadedOperatorKind OpKind) {
352  if (const auto *BinOp = checkOpKind<TExpr>(Part, OpKind)) {
353  const std::pair<const Expr *, const Expr *> Operands = getOperands(BinOp);
354  if (areEquivalentExpr(Operands.first, Operands.second))
355  return true;
356  return collectOperands<TExpr>(Operands.first, AllOperands, OpKind) ||
357  collectOperands<TExpr>(Operands.second, AllOperands, OpKind);
358  }
359 
360  AllOperands.push_back(Part);
361  return false;
362 }
363 
364 template <typename TExpr>
365 static bool hasSameOperatorParent(const Expr *TheExpr,
366  OverloadedOperatorKind OpKind,
367  ASTContext &Context) {
368  // IgnoreParenImpCasts logic in reverse: skip surrounding uninteresting nodes
369  const DynTypedNodeList Parents = Context.getParents(*TheExpr);
370  for (DynTypedNode DynParent : Parents) {
371  if (const auto *Parent = DynParent.get<Expr>()) {
372  bool Skip = isa<ParenExpr>(Parent) || isa<ImplicitCastExpr>(Parent) ||
373  isa<FullExpr>(Parent) ||
374  isa<MaterializeTemporaryExpr>(Parent);
375  if (Skip && hasSameOperatorParent<TExpr>(Parent, OpKind, Context))
376  return true;
377  if (checkOpKind<TExpr>(Parent, OpKind))
378  return true;
379  }
380  }
381 
382  return false;
383 }
384 
385 template <typename TExpr>
386 static bool
387 markDuplicateOperands(const TExpr *TheExpr,
388  ast_matchers::internal::BoundNodesTreeBuilder *Builder,
389  ASTContext &Context) {
390  const OverloadedOperatorKind OpKind = getOp(TheExpr);
391  if (OpKind == OO_None)
392  return false;
393  // if there are no nested operators of the same kind, it's handled by
394  // operands/parametersAreEquivalent
395  const std::pair<const Expr *, const Expr *> Operands = getOperands(TheExpr);
396  if (!(checkOpKind<TExpr>(Operands.first, OpKind) ||
397  checkOpKind<TExpr>(Operands.second, OpKind)))
398  return false;
399 
400  // if parent is the same kind of operator, it's handled by a previous call to
401  // markDuplicateOperands
402  if (hasSameOperatorParent<TExpr>(TheExpr, OpKind, Context))
403  return false;
404 
405  SmallVector<const Expr *, 4> AllOperands;
406  if (collectOperands<TExpr>(Operands.first, AllOperands, OpKind))
407  return false;
408  if (collectOperands<TExpr>(Operands.second, AllOperands, OpKind))
409  return false;
410  size_t NumOperands = AllOperands.size();
411  llvm::SmallBitVector Duplicates(NumOperands);
412  for (size_t I = 0; I < NumOperands; I++) {
413  if (Duplicates[I])
414  continue;
415  bool FoundDuplicates = false;
416 
417  for (size_t J = I + 1; J < NumOperands; J++) {
418  if (AllOperands[J]->HasSideEffects(Context))
419  break;
420 
421  if (areEquivalentExpr(AllOperands[I], AllOperands[J])) {
422  FoundDuplicates = true;
423  Duplicates.set(J);
424  Builder->setBinding(SmallString<11>(llvm::formatv("duplicate{0}", J)),
425  DynTypedNode::create(*AllOperands[J]));
426  }
427  }
428 
429  if (FoundDuplicates)
430  Builder->setBinding(SmallString<11>(llvm::formatv("duplicate{0}", I)),
431  DynTypedNode::create(*AllOperands[I]));
432  }
433 
434  return Duplicates.any();
435 }
436 
437 AST_MATCHER(Expr, isIntegerConstantExpr) {
438  if (Node.isInstantiationDependent())
439  return false;
440  return Node.isIntegerConstantExpr(Finder->getASTContext());
441 }
442 
443 AST_MATCHER(BinaryOperator, operandsAreEquivalent) {
444  return areEquivalentExpr(Node.getLHS(), Node.getRHS());
445 }
446 
447 AST_MATCHER(BinaryOperator, nestedOperandsAreEquivalent) {
448  return markDuplicateOperands(&Node, Builder, Finder->getASTContext());
449 }
450 
451 AST_MATCHER(ConditionalOperator, expressionsAreEquivalent) {
452  return areEquivalentExpr(Node.getTrueExpr(), Node.getFalseExpr());
453 }
454 
455 AST_MATCHER(CallExpr, parametersAreEquivalent) {
456  return Node.getNumArgs() == 2 &&
457  areEquivalentExpr(Node.getArg(0), Node.getArg(1));
458 }
459 
460 AST_MATCHER(CXXOperatorCallExpr, nestedParametersAreEquivalent) {
461  return markDuplicateOperands(&Node, Builder, Finder->getASTContext());
462 }
463 
464 AST_MATCHER(BinaryOperator, binaryOperatorIsInMacro) {
465  return Node.getOperatorLoc().isMacroID();
466 }
467 
468 AST_MATCHER(ConditionalOperator, conditionalOperatorIsInMacro) {
469  return Node.getQuestionLoc().isMacroID() || Node.getColonLoc().isMacroID();
470 }
471 
472 AST_MATCHER(Expr, isMacro) { return Node.getExprLoc().isMacroID(); }
473 
474 AST_MATCHER_P(Expr, expandedByMacro, ArrayRef<llvm::StringLiteral>, Names) {
475  const SourceManager &SM = Finder->getASTContext().getSourceManager();
476  const LangOptions &LO = Finder->getASTContext().getLangOpts();
477  SourceLocation Loc = Node.getExprLoc();
478  while (Loc.isMacroID()) {
479  StringRef MacroName = Lexer::getImmediateMacroName(Loc, SM, LO);
480  if (llvm::is_contained(Names, MacroName))
481  return true;
482  Loc = SM.getImmediateMacroCallerLoc(Loc);
483  }
484  return false;
485 }
486 
487 // Returns a matcher for integer constant expressions.
488 static ast_matchers::internal::Matcher<Expr>
489 matchIntegerConstantExpr(StringRef Id) {
490  std::string CstId = (Id + "-const").str();
491  return expr(isIntegerConstantExpr()).bind(CstId);
492 }
493 
494 // Retrieves the integer expression matched by 'matchIntegerConstantExpr' with
495 // name 'Id' and stores it into 'ConstExpr', the value of the expression is
496 // stored into `Value`.
497 static bool retrieveIntegerConstantExpr(const MatchFinder::MatchResult &Result,
498  StringRef Id, APSInt &Value,
499  const Expr *&ConstExpr) {
500  std::string CstId = (Id + "-const").str();
501  ConstExpr = Result.Nodes.getNodeAs<Expr>(CstId);
502  if (!ConstExpr)
503  return false;
504  Optional<llvm::APSInt> R = ConstExpr->getIntegerConstantExpr(*Result.Context);
505  if (!R)
506  return false;
507  Value = *R;
508  return true;
509 }
510 
511 // Overloaded `retrieveIntegerConstantExpr` for compatibility.
512 static bool retrieveIntegerConstantExpr(const MatchFinder::MatchResult &Result,
513  StringRef Id, APSInt &Value) {
514  const Expr *ConstExpr = nullptr;
515  return retrieveIntegerConstantExpr(Result, Id, Value, ConstExpr);
516 }
517 
518 // Returns a matcher for symbolic expressions (matches every expression except
519 // ingeter constant expressions).
520 static ast_matchers::internal::Matcher<Expr> matchSymbolicExpr(StringRef Id) {
521  std::string SymId = (Id + "-sym").str();
522  return ignoringParenImpCasts(
523  expr(unless(isIntegerConstantExpr())).bind(SymId));
524 }
525 
526 // Retrieves the expression matched by 'matchSymbolicExpr' with name 'Id' and
527 // stores it into 'SymExpr'.
528 static bool retrieveSymbolicExpr(const MatchFinder::MatchResult &Result,
529  StringRef Id, const Expr *&SymExpr) {
530  std::string SymId = (Id + "-sym").str();
531  if (const auto *Node = Result.Nodes.getNodeAs<Expr>(SymId)) {
532  SymExpr = Node;
533  return true;
534  }
535  return false;
536 }
537 
538 // Match a binary operator between a symbolic expression and an integer constant
539 // expression.
540 static ast_matchers::internal::Matcher<Expr>
541 matchBinOpIntegerConstantExpr(StringRef Id) {
542  const auto BinOpCstExpr =
543  expr(anyOf(binaryOperator(hasAnyOperatorName("+", "|", "&"),
544  hasOperands(matchSymbolicExpr(Id),
545  matchIntegerConstantExpr(Id))),
546  binaryOperator(hasOperatorName("-"),
547  hasLHS(matchSymbolicExpr(Id)),
548  hasRHS(matchIntegerConstantExpr(Id)))))
549  .bind(Id);
550  return ignoringParenImpCasts(BinOpCstExpr);
551 }
552 
553 // Retrieves sub-expressions matched by 'matchBinOpIntegerConstantExpr' with
554 // name 'Id'.
555 static bool
556 retrieveBinOpIntegerConstantExpr(const MatchFinder::MatchResult &Result,
557  StringRef Id, BinaryOperatorKind &Opcode,
558  const Expr *&Symbol, APSInt &Value) {
559  if (const auto *BinExpr = Result.Nodes.getNodeAs<BinaryOperator>(Id)) {
560  Opcode = BinExpr->getOpcode();
561  return retrieveSymbolicExpr(Result, Id, Symbol) &&
562  retrieveIntegerConstantExpr(Result, Id, Value);
563  }
564  return false;
565 }
566 
567 // Matches relational expressions: 'Expr <op> k' (i.e. x < 2, x != 3, 12 <= x).
568 static ast_matchers::internal::Matcher<Expr>
569 matchRelationalIntegerConstantExpr(StringRef Id) {
570  std::string CastId = (Id + "-cast").str();
571  std::string SwapId = (Id + "-swap").str();
572  std::string NegateId = (Id + "-negate").str();
573  std::string OverloadId = (Id + "-overload").str();
574  std::string ConstId = (Id + "-const").str();
575 
576  const auto RelationalExpr = ignoringParenImpCasts(binaryOperator(
577  isComparisonOperator(), expr().bind(Id),
578  anyOf(allOf(hasLHS(matchSymbolicExpr(Id)),
579  hasRHS(matchIntegerConstantExpr(Id))),
580  allOf(hasLHS(matchIntegerConstantExpr(Id)),
581  hasRHS(matchSymbolicExpr(Id)), expr().bind(SwapId)))));
582 
583  // A cast can be matched as a comparator to zero. (i.e. if (x) is equivalent
584  // to if (x != 0)).
585  const auto CastExpr =
586  implicitCastExpr(hasCastKind(CK_IntegralToBoolean),
587  hasSourceExpression(matchSymbolicExpr(Id)))
588  .bind(CastId);
589 
590  const auto NegateRelationalExpr =
591  unaryOperator(hasOperatorName("!"),
592  hasUnaryOperand(anyOf(CastExpr, RelationalExpr)))
593  .bind(NegateId);
594 
595  // Do not bind to double negation.
596  const auto NegateNegateRelationalExpr =
597  unaryOperator(hasOperatorName("!"),
598  hasUnaryOperand(unaryOperator(
599  hasOperatorName("!"),
600  hasUnaryOperand(anyOf(CastExpr, RelationalExpr)))));
601 
602  const auto OverloadedOperatorExpr =
603  cxxOperatorCallExpr(
604  hasAnyOverloadedOperatorName("==", "!=", "<", "<=", ">", ">="),
605  // Filter noisy false positives.
606  unless(isMacro()), unless(isInTemplateInstantiation()),
607  anyOf(hasLHS(ignoringParenImpCasts(integerLiteral().bind(ConstId))),
608  hasRHS(ignoringParenImpCasts(integerLiteral().bind(ConstId)))))
609  .bind(OverloadId);
610 
611  return anyOf(RelationalExpr, CastExpr, NegateRelationalExpr,
612  NegateNegateRelationalExpr, OverloadedOperatorExpr);
613 }
614 
615 // Checks whether a function param is non constant reference type, and may
616 // be modified in the function.
617 static bool isNonConstReferenceType(QualType ParamType) {
618  return ParamType->isReferenceType() &&
619  !ParamType.getNonReferenceType().isConstQualified();
620 }
621 
622 // Checks whether the arguments of an overloaded operator can be modified in the
623 // function.
624 // For operators that take an instance and a constant as arguments, only the
625 // first argument (the instance) needs to be checked, since the constant itself
626 // is a temporary expression. Whether the second parameter is checked is
627 // controlled by the parameter `ParamsToCheckCount`.
628 static bool
629 canOverloadedOperatorArgsBeModified(const CXXOperatorCallExpr *OperatorCall,
630  bool CheckSecondParam) {
631  const auto *OperatorDecl =
632  dyn_cast_or_null<FunctionDecl>(OperatorCall->getCalleeDecl());
633  // if we can't find the declaration, conservatively assume it can modify
634  // arguments
635  if (!OperatorDecl)
636  return true;
637 
638  unsigned ParamCount = OperatorDecl->getNumParams();
639 
640  // Overloaded operators declared inside a class have only one param.
641  // These functions must be declared const in order to not be able to modify
642  // the instance of the class they are called through.
643  if (ParamCount == 1 &&
644  !OperatorDecl->getType()->castAs<FunctionType>()->isConst())
645  return true;
646 
647  if (isNonConstReferenceType(OperatorDecl->getParamDecl(0)->getType()))
648  return true;
649 
650  return CheckSecondParam && ParamCount == 2 &&
651  isNonConstReferenceType(OperatorDecl->getParamDecl(1)->getType());
652 }
653 
654 // Retrieves sub-expressions matched by 'matchRelationalIntegerConstantExpr'
655 // with name 'Id'.
656 static bool retrieveRelationalIntegerConstantExpr(
657  const MatchFinder::MatchResult &Result, StringRef Id,
658  const Expr *&OperandExpr, BinaryOperatorKind &Opcode, const Expr *&Symbol,
659  APSInt &Value, const Expr *&ConstExpr) {
660  std::string CastId = (Id + "-cast").str();
661  std::string SwapId = (Id + "-swap").str();
662  std::string NegateId = (Id + "-negate").str();
663  std::string OverloadId = (Id + "-overload").str();
664 
665  if (const auto *Bin = Result.Nodes.getNodeAs<BinaryOperator>(Id)) {
666  // Operand received with explicit comparator.
667  Opcode = Bin->getOpcode();
668  OperandExpr = Bin;
669 
670  if (!retrieveIntegerConstantExpr(Result, Id, Value, ConstExpr))
671  return false;
672  } else if (const auto *Cast = Result.Nodes.getNodeAs<CastExpr>(CastId)) {
673  // Operand received with implicit comparator (cast).
674  Opcode = BO_NE;
675  OperandExpr = Cast;
676  Value = APSInt(32, false);
677  } else if (const auto *OverloadedOperatorExpr =
678  Result.Nodes.getNodeAs<CXXOperatorCallExpr>(OverloadId)) {
679  if (canOverloadedOperatorArgsBeModified(OverloadedOperatorExpr, false))
680  return false;
681 
682  bool IntegerConstantIsFirstArg = false;
683 
684  if (const auto *Arg = OverloadedOperatorExpr->getArg(1)) {
685  if (!Arg->isValueDependent() &&
686  !Arg->isIntegerConstantExpr(*Result.Context)) {
687  IntegerConstantIsFirstArg = true;
688  if (const auto *Arg = OverloadedOperatorExpr->getArg(0)) {
689  if (!Arg->isValueDependent() &&
690  !Arg->isIntegerConstantExpr(*Result.Context))
691  return false;
692  } else
693  return false;
694  }
695  } else
696  return false;
697 
698  Symbol = OverloadedOperatorExpr->getArg(IntegerConstantIsFirstArg ? 1 : 0);
699  OperandExpr = OverloadedOperatorExpr;
700  Opcode = BinaryOperator::getOverloadedOpcode(OverloadedOperatorExpr->getOperator());
701 
702  if (!retrieveIntegerConstantExpr(Result, Id, Value, ConstExpr))
703  return false;
704 
705  if (!BinaryOperator::isComparisonOp(Opcode))
706  return false;
707 
708  // The call site of this function expects the constant on the RHS,
709  // so change the opcode accordingly.
710  if (IntegerConstantIsFirstArg)
711  Opcode = BinaryOperator::reverseComparisonOp(Opcode);
712 
713  return true;
714  } else {
715  return false;
716  }
717 
718  if (!retrieveSymbolicExpr(Result, Id, Symbol))
719  return false;
720 
721  if (Result.Nodes.getNodeAs<Expr>(SwapId))
722  Opcode = BinaryOperator::reverseComparisonOp(Opcode);
723  if (Result.Nodes.getNodeAs<Expr>(NegateId))
724  Opcode = BinaryOperator::negateComparisonOp(Opcode);
725  return true;
726 }
727 
728 // Checks for expressions like (X == 4) && (Y != 9)
729 static bool areSidesBinaryConstExpressions(const BinaryOperator *&BinOp, const ASTContext *AstCtx) {
730  const auto *LhsBinOp = dyn_cast<BinaryOperator>(BinOp->getLHS());
731  const auto *RhsBinOp = dyn_cast<BinaryOperator>(BinOp->getRHS());
732 
733  if (!LhsBinOp || !RhsBinOp)
734  return false;
735 
736  auto IsIntegerConstantExpr = [AstCtx](const Expr *E) {
737  return !E->isValueDependent() && E->isIntegerConstantExpr(*AstCtx);
738  };
739 
740  if ((IsIntegerConstantExpr(LhsBinOp->getLHS()) ||
741  IsIntegerConstantExpr(LhsBinOp->getRHS())) &&
742  (IsIntegerConstantExpr(RhsBinOp->getLHS()) ||
743  IsIntegerConstantExpr(RhsBinOp->getRHS())))
744  return true;
745  return false;
746 }
747 
748 // Retrieves integer constant subexpressions from binary operator expressions
749 // that have two equivalent sides.
750 // E.g.: from (X == 5) && (X == 5) retrieves 5 and 5.
751 static bool retrieveConstExprFromBothSides(const BinaryOperator *&BinOp,
752  BinaryOperatorKind &MainOpcode,
753  BinaryOperatorKind &SideOpcode,
754  const Expr *&LhsConst,
755  const Expr *&RhsConst,
756  const ASTContext *AstCtx) {
757  assert(areSidesBinaryConstExpressions(BinOp, AstCtx) &&
758  "Both sides of binary operator must be constant expressions!");
759 
760  MainOpcode = BinOp->getOpcode();
761 
762  const auto *BinOpLhs = cast<BinaryOperator>(BinOp->getLHS());
763  const auto *BinOpRhs = cast<BinaryOperator>(BinOp->getRHS());
764 
765  auto IsIntegerConstantExpr = [AstCtx](const Expr *E) {
766  return !E->isValueDependent() && E->isIntegerConstantExpr(*AstCtx);
767  };
768 
769  LhsConst = IsIntegerConstantExpr(BinOpLhs->getLHS()) ? BinOpLhs->getLHS()
770  : BinOpLhs->getRHS();
771  RhsConst = IsIntegerConstantExpr(BinOpRhs->getLHS()) ? BinOpRhs->getLHS()
772  : BinOpRhs->getRHS();
773 
774  if (!LhsConst || !RhsConst)
775  return false;
776 
777  assert(BinOpLhs->getOpcode() == BinOpRhs->getOpcode() &&
778  "Sides of the binary operator must be equivalent expressions!");
779 
780  SideOpcode = BinOpLhs->getOpcode();
781 
782  return true;
783 }
784 
785 static bool isSameRawIdentifierToken(const Token &T1, const Token &T2,
786  const SourceManager &SM) {
787  if (T1.getKind() != T2.getKind())
788  return false;
789  if (T1.isNot(tok::raw_identifier))
790  return true;
791  if (T1.getLength() != T2.getLength())
792  return false;
793  return StringRef(SM.getCharacterData(T1.getLocation()), T1.getLength()) ==
794  StringRef(SM.getCharacterData(T2.getLocation()), T2.getLength());
795 }
796 
797 bool isTokAtEndOfExpr(SourceRange ExprSR, Token T, const SourceManager &SM) {
798  return SM.getExpansionLoc(ExprSR.getEnd()) == T.getLocation();
799 }
800 
801 /// Returns true if both LhsExpr and RhsExpr are
802 /// macro expressions and they are expanded
803 /// from different macros.
804 static bool areExprsFromDifferentMacros(const Expr *LhsExpr,
805  const Expr *RhsExpr,
806  const ASTContext *AstCtx) {
807  if (!LhsExpr || !RhsExpr)
808  return false;
809  SourceRange Lsr = LhsExpr->getSourceRange();
810  SourceRange Rsr = RhsExpr->getSourceRange();
811  if (!Lsr.getBegin().isMacroID() || !Rsr.getBegin().isMacroID())
812  return false;
813 
814  const SourceManager &SM = AstCtx->getSourceManager();
815  const LangOptions &LO = AstCtx->getLangOpts();
816 
817  std::pair<FileID, unsigned> LsrLocInfo =
818  SM.getDecomposedLoc(SM.getExpansionLoc(Lsr.getBegin()));
819  std::pair<FileID, unsigned> RsrLocInfo =
820  SM.getDecomposedLoc(SM.getExpansionLoc(Rsr.getBegin()));
821  llvm::MemoryBufferRef MB = SM.getBufferOrFake(LsrLocInfo.first);
822 
823  const char *LTokenPos = MB.getBufferStart() + LsrLocInfo.second;
824  const char *RTokenPos = MB.getBufferStart() + RsrLocInfo.second;
825  Lexer LRawLex(SM.getLocForStartOfFile(LsrLocInfo.first), LO,
826  MB.getBufferStart(), LTokenPos, MB.getBufferEnd());
827  Lexer RRawLex(SM.getLocForStartOfFile(RsrLocInfo.first), LO,
828  MB.getBufferStart(), RTokenPos, MB.getBufferEnd());
829 
830  Token LTok, RTok;
831  do { // Compare the expressions token-by-token.
832  LRawLex.LexFromRawLexer(LTok);
833  RRawLex.LexFromRawLexer(RTok);
834  } while (!LTok.is(tok::eof) && !RTok.is(tok::eof) &&
835  isSameRawIdentifierToken(LTok, RTok, SM) &&
836  !isTokAtEndOfExpr(Lsr, LTok, SM) &&
837  !isTokAtEndOfExpr(Rsr, RTok, SM));
838  return (!isTokAtEndOfExpr(Lsr, LTok, SM) ||
839  !isTokAtEndOfExpr(Rsr, RTok, SM)) ||
840  !isSameRawIdentifierToken(LTok, RTok, SM);
841 }
842 
843 static bool areExprsMacroAndNonMacro(const Expr *&LhsExpr,
844  const Expr *&RhsExpr) {
845  if (!LhsExpr || !RhsExpr)
846  return false;
847 
848  SourceLocation LhsLoc = LhsExpr->getExprLoc();
849  SourceLocation RhsLoc = RhsExpr->getExprLoc();
850 
851  return LhsLoc.isMacroID() != RhsLoc.isMacroID();
852 }
853 } // namespace
854 
855 void RedundantExpressionCheck::registerMatchers(MatchFinder *Finder) {
856  const auto AnyLiteralExpr = ignoringParenImpCasts(
857  anyOf(cxxBoolLiteral(), characterLiteral(), integerLiteral()));
858 
859  const auto BannedIntegerLiteral =
860  integerLiteral(expandedByMacro(KnownBannedMacroNames));
861 
862  // Binary with equivalent operands, like (X != 2 && X != 2).
863  Finder->addMatcher(
864  traverse(TK_AsIs,
865  binaryOperator(
866  anyOf(isComparisonOperator(),
867  hasAnyOperatorName("-", "/", "%", "|", "&", "^", "&&",
868  "||", "=")),
869  operandsAreEquivalent(),
870  // Filter noisy false positives.
871  unless(isInTemplateInstantiation()),
872  unless(binaryOperatorIsInMacro()),
873  unless(hasType(realFloatingPointType())),
874  unless(hasEitherOperand(hasType(realFloatingPointType()))),
875  unless(hasLHS(AnyLiteralExpr)),
876  unless(hasDescendant(BannedIntegerLiteral)))
877  .bind("binary")),
878  this);
879 
880  // Logical or bitwise operator with equivalent nested operands, like (X && Y
881  // && X) or (X && (Y && X))
882  Finder->addMatcher(
883  binaryOperator(hasAnyOperatorName("|", "&", "||", "&&", "^"),
884  nestedOperandsAreEquivalent(),
885  // Filter noisy false positives.
886  unless(isInTemplateInstantiation()),
887  unless(binaryOperatorIsInMacro()),
888  // TODO: if the banned macros are themselves duplicated
889  unless(hasDescendant(BannedIntegerLiteral)))
890  .bind("nested-duplicates"),
891  this);
892 
893  // Conditional (ternary) operator with equivalent operands, like (Y ? X : X).
894  Finder->addMatcher(
895  traverse(TK_AsIs,
896  conditionalOperator(expressionsAreEquivalent(),
897  // Filter noisy false positives.
898  unless(conditionalOperatorIsInMacro()),
899  unless(isInTemplateInstantiation()))
900  .bind("cond")),
901  this);
902 
903  // Overloaded operators with equivalent operands.
904  Finder->addMatcher(
905  traverse(TK_AsIs,
906  cxxOperatorCallExpr(
907  hasAnyOverloadedOperatorName("-", "/", "%", "|", "&", "^",
908  "==", "!=", "<", "<=", ">",
909  ">=", "&&", "||", "="),
910  parametersAreEquivalent(),
911  // Filter noisy false positives.
912  unless(isMacro()), unless(isInTemplateInstantiation()))
913  .bind("call")),
914  this);
915 
916  // Overloaded operators with equivalent operands.
917  Finder->addMatcher(
918  cxxOperatorCallExpr(
919  hasAnyOverloadedOperatorName("|", "&", "||", "&&", "^"),
920  nestedParametersAreEquivalent(), argumentCountIs(2),
921  // Filter noisy false positives.
922  unless(isMacro()), unless(isInTemplateInstantiation()))
923  .bind("nested-duplicates"),
924  this);
925 
926  // Match expressions like: !(1 | 2 | 3)
927  Finder->addMatcher(
928  traverse(TK_AsIs,
929  implicitCastExpr(
930  hasImplicitDestinationType(isInteger()),
931  has(unaryOperator(
932  hasOperatorName("!"),
933  hasUnaryOperand(ignoringParenImpCasts(binaryOperator(
934  hasAnyOperatorName("|", "&"),
935  hasLHS(anyOf(
936  binaryOperator(hasAnyOperatorName("|", "&")),
937  integerLiteral())),
938  hasRHS(integerLiteral())))))
939  .bind("logical-bitwise-confusion")))),
940  this);
941 
942  // Match expressions like: (X << 8) & 0xFF
943  Finder->addMatcher(
944  traverse(TK_AsIs,
945  binaryOperator(
946  hasOperatorName("&"),
947  hasOperands(ignoringParenImpCasts(binaryOperator(
948  hasOperatorName("<<"),
949  hasRHS(ignoringParenImpCasts(
950  integerLiteral().bind("shift-const"))))),
951  ignoringParenImpCasts(
952  integerLiteral().bind("and-const"))))
953  .bind("left-right-shift-confusion")),
954  this);
955 
956  // Match common expressions and apply more checks to find redundant
957  // sub-expressions.
958  // a) Expr <op> K1 == K2
959  // b) Expr <op> K1 == Expr
960  // c) Expr <op> K1 == Expr <op> K2
961  // see: 'checkArithmeticExpr' and 'checkBitwiseExpr'
962  const auto BinOpCstLeft = matchBinOpIntegerConstantExpr("lhs");
963  const auto BinOpCstRight = matchBinOpIntegerConstantExpr("rhs");
964  const auto CstRight = matchIntegerConstantExpr("rhs");
965  const auto SymRight = matchSymbolicExpr("rhs");
966 
967  // Match expressions like: x <op> 0xFF == 0xF00.
968  Finder->addMatcher(
969  traverse(TK_AsIs, binaryOperator(isComparisonOperator(),
970  hasOperands(BinOpCstLeft, CstRight))
971  .bind("binop-const-compare-to-const")),
972  this);
973 
974  // Match expressions like: x <op> 0xFF == x.
975  Finder->addMatcher(
976  traverse(
977  TK_AsIs,
978  binaryOperator(isComparisonOperator(),
979  anyOf(allOf(hasLHS(BinOpCstLeft), hasRHS(SymRight)),
980  allOf(hasLHS(SymRight), hasRHS(BinOpCstLeft))))
981  .bind("binop-const-compare-to-sym")),
982  this);
983 
984  // Match expressions like: x <op> 10 == x <op> 12.
985  Finder->addMatcher(
986  traverse(TK_AsIs,
987  binaryOperator(isComparisonOperator(), hasLHS(BinOpCstLeft),
988  hasRHS(BinOpCstRight),
989  // Already reported as redundant.
990  unless(operandsAreEquivalent()))
991  .bind("binop-const-compare-to-binop-const")),
992  this);
993 
994  // Match relational expressions combined with logical operators and find
995  // redundant sub-expressions.
996  // see: 'checkRelationalExpr'
997 
998  // Match expressions like: x < 2 && x > 2.
999  const auto ComparisonLeft = matchRelationalIntegerConstantExpr("lhs");
1000  const auto ComparisonRight = matchRelationalIntegerConstantExpr("rhs");
1001  Finder->addMatcher(
1002  traverse(TK_AsIs,
1003  binaryOperator(hasAnyOperatorName("||", "&&"),
1004  hasLHS(ComparisonLeft), hasRHS(ComparisonRight),
1005  // Already reported as redundant.
1006  unless(operandsAreEquivalent()))
1007  .bind("comparisons-of-symbol-and-const")),
1008  this);
1009 }
1010 
1011 void RedundantExpressionCheck::checkArithmeticExpr(
1012  const MatchFinder::MatchResult &Result) {
1013  APSInt LhsValue, RhsValue;
1014  const Expr *LhsSymbol = nullptr, *RhsSymbol = nullptr;
1015  BinaryOperatorKind LhsOpcode, RhsOpcode;
1016 
1017  if (const auto *ComparisonOperator = Result.Nodes.getNodeAs<BinaryOperator>(
1018  "binop-const-compare-to-sym")) {
1019  BinaryOperatorKind Opcode = ComparisonOperator->getOpcode();
1020  if (!retrieveBinOpIntegerConstantExpr(Result, "lhs", LhsOpcode, LhsSymbol,
1021  LhsValue) ||
1022  !retrieveSymbolicExpr(Result, "rhs", RhsSymbol) ||
1023  !areEquivalentExpr(LhsSymbol, RhsSymbol))
1024  return;
1025 
1026  // Check expressions: x + k == x or x - k == x.
1027  if (LhsOpcode == BO_Add || LhsOpcode == BO_Sub) {
1028  if ((LhsValue != 0 && Opcode == BO_EQ) ||
1029  (LhsValue == 0 && Opcode == BO_NE))
1030  diag(ComparisonOperator->getOperatorLoc(),
1031  "logical expression is always false");
1032  else if ((LhsValue == 0 && Opcode == BO_EQ) ||
1033  (LhsValue != 0 && Opcode == BO_NE))
1034  diag(ComparisonOperator->getOperatorLoc(),
1035  "logical expression is always true");
1036  }
1037  } else if (const auto *ComparisonOperator =
1038  Result.Nodes.getNodeAs<BinaryOperator>(
1039  "binop-const-compare-to-binop-const")) {
1040  BinaryOperatorKind Opcode = ComparisonOperator->getOpcode();
1041 
1042  if (!retrieveBinOpIntegerConstantExpr(Result, "lhs", LhsOpcode, LhsSymbol,
1043  LhsValue) ||
1044  !retrieveBinOpIntegerConstantExpr(Result, "rhs", RhsOpcode, RhsSymbol,
1045  RhsValue) ||
1046  !areEquivalentExpr(LhsSymbol, RhsSymbol))
1047  return;
1048 
1049  transformSubToCanonicalAddExpr(LhsOpcode, LhsValue);
1050  transformSubToCanonicalAddExpr(RhsOpcode, RhsValue);
1051 
1052  // Check expressions: x + 1 == x + 2 or x + 1 != x + 2.
1053  if (LhsOpcode == BO_Add && RhsOpcode == BO_Add) {
1054  if ((Opcode == BO_EQ && APSInt::compareValues(LhsValue, RhsValue) == 0) ||
1055  (Opcode == BO_NE && APSInt::compareValues(LhsValue, RhsValue) != 0)) {
1056  diag(ComparisonOperator->getOperatorLoc(),
1057  "logical expression is always true");
1058  } else if ((Opcode == BO_EQ &&
1059  APSInt::compareValues(LhsValue, RhsValue) != 0) ||
1060  (Opcode == BO_NE &&
1061  APSInt::compareValues(LhsValue, RhsValue) == 0)) {
1062  diag(ComparisonOperator->getOperatorLoc(),
1063  "logical expression is always false");
1064  }
1065  }
1066  }
1067 }
1068 
1069 static bool exprEvaluatesToZero(BinaryOperatorKind Opcode, APSInt Value) {
1070  return (Opcode == BO_And || Opcode == BO_AndAssign) && Value == 0;
1071 }
1072 
1073 static bool exprEvaluatesToBitwiseNegatedZero(BinaryOperatorKind Opcode,
1074  APSInt Value) {
1075  return (Opcode == BO_Or || Opcode == BO_OrAssign) && ~Value == 0;
1076 }
1077 
1078 static bool exprEvaluatesToSymbolic(BinaryOperatorKind Opcode, APSInt Value) {
1079  return ((Opcode == BO_Or || Opcode == BO_OrAssign) && Value == 0) ||
1080  ((Opcode == BO_And || Opcode == BO_AndAssign) && ~Value == 0);
1081 }
1082 
1083 
1084 void RedundantExpressionCheck::checkBitwiseExpr(
1085  const MatchFinder::MatchResult &Result) {
1086  if (const auto *ComparisonOperator = Result.Nodes.getNodeAs<BinaryOperator>(
1087  "binop-const-compare-to-const")) {
1088  BinaryOperatorKind Opcode = ComparisonOperator->getOpcode();
1089 
1090  APSInt LhsValue, RhsValue;
1091  const Expr *LhsSymbol = nullptr;
1092  BinaryOperatorKind LhsOpcode;
1093  if (!retrieveBinOpIntegerConstantExpr(Result, "lhs", LhsOpcode, LhsSymbol,
1094  LhsValue) ||
1095  !retrieveIntegerConstantExpr(Result, "rhs", RhsValue))
1096  return;
1097 
1098  uint64_t LhsConstant = LhsValue.getZExtValue();
1099  uint64_t RhsConstant = RhsValue.getZExtValue();
1100  SourceLocation Loc = ComparisonOperator->getOperatorLoc();
1101 
1102  // Check expression: x & k1 == k2 (i.e. x & 0xFF == 0xF00)
1103  if (LhsOpcode == BO_And && (LhsConstant & RhsConstant) != RhsConstant) {
1104  if (Opcode == BO_EQ)
1105  diag(Loc, "logical expression is always false");
1106  else if (Opcode == BO_NE)
1107  diag(Loc, "logical expression is always true");
1108  }
1109 
1110  // Check expression: x | k1 == k2 (i.e. x | 0xFF == 0xF00)
1111  if (LhsOpcode == BO_Or && (LhsConstant | RhsConstant) != RhsConstant) {
1112  if (Opcode == BO_EQ)
1113  diag(Loc, "logical expression is always false");
1114  else if (Opcode == BO_NE)
1115  diag(Loc, "logical expression is always true");
1116  }
1117  } else if (const auto *IneffectiveOperator =
1118  Result.Nodes.getNodeAs<BinaryOperator>(
1119  "ineffective-bitwise")) {
1120  APSInt Value;
1121  const Expr *Sym = nullptr, *ConstExpr = nullptr;
1122 
1123  if (!retrieveSymbolicExpr(Result, "ineffective-bitwise", Sym) ||
1124  !retrieveIntegerConstantExpr(Result, "ineffective-bitwise", Value,
1125  ConstExpr))
1126  return;
1127 
1128  if((Value != 0 && ~Value != 0) || Sym->getExprLoc().isMacroID())
1129  return;
1130 
1131  SourceLocation Loc = IneffectiveOperator->getOperatorLoc();
1132 
1133  BinaryOperatorKind Opcode = IneffectiveOperator->getOpcode();
1134  if (exprEvaluatesToZero(Opcode, Value)) {
1135  diag(Loc, "expression always evaluates to 0");
1136  } else if (exprEvaluatesToBitwiseNegatedZero(Opcode, Value)) {
1137  SourceRange ConstExprRange(ConstExpr->getBeginLoc(),
1138  ConstExpr->getEndLoc());
1139  StringRef ConstExprText = Lexer::getSourceText(
1140  CharSourceRange::getTokenRange(ConstExprRange), *Result.SourceManager,
1141  Result.Context->getLangOpts());
1142 
1143  diag(Loc, "expression always evaluates to '%0'") << ConstExprText;
1144 
1145  } else if (exprEvaluatesToSymbolic(Opcode, Value)) {
1146  SourceRange SymExprRange(Sym->getBeginLoc(), Sym->getEndLoc());
1147 
1148  StringRef ExprText = Lexer::getSourceText(
1149  CharSourceRange::getTokenRange(SymExprRange), *Result.SourceManager,
1150  Result.Context->getLangOpts());
1151 
1152  diag(Loc, "expression always evaluates to '%0'") << ExprText;
1153  }
1154  }
1155 }
1156 
1157 void RedundantExpressionCheck::checkRelationalExpr(
1158  const MatchFinder::MatchResult &Result) {
1159  if (const auto *ComparisonOperator = Result.Nodes.getNodeAs<BinaryOperator>(
1160  "comparisons-of-symbol-and-const")) {
1161  // Matched expressions are: (x <op> k1) <REL> (x <op> k2).
1162  // E.g.: (X < 2) && (X > 4)
1163  BinaryOperatorKind Opcode = ComparisonOperator->getOpcode();
1164 
1165  const Expr *LhsExpr = nullptr, *RhsExpr = nullptr;
1166  const Expr *LhsSymbol = nullptr, *RhsSymbol = nullptr;
1167  const Expr *LhsConst = nullptr, *RhsConst = nullptr;
1168  BinaryOperatorKind LhsOpcode, RhsOpcode;
1169  APSInt LhsValue, RhsValue;
1170 
1171  if (!retrieveRelationalIntegerConstantExpr(
1172  Result, "lhs", LhsExpr, LhsOpcode, LhsSymbol, LhsValue, LhsConst) ||
1173  !retrieveRelationalIntegerConstantExpr(
1174  Result, "rhs", RhsExpr, RhsOpcode, RhsSymbol, RhsValue, RhsConst) ||
1175  !areEquivalentExpr(LhsSymbol, RhsSymbol))
1176  return;
1177 
1178  // Bring expr to a canonical form: smallest constant must be on the left.
1179  if (APSInt::compareValues(LhsValue, RhsValue) > 0) {
1180  std::swap(LhsExpr, RhsExpr);
1181  std::swap(LhsValue, RhsValue);
1182  std::swap(LhsSymbol, RhsSymbol);
1183  std::swap(LhsOpcode, RhsOpcode);
1184  }
1185 
1186  // Constants come from two different macros, or one of them is a macro.
1187  if (areExprsFromDifferentMacros(LhsConst, RhsConst, Result.Context) ||
1188  areExprsMacroAndNonMacro(LhsConst, RhsConst))
1189  return;
1190 
1191  if ((Opcode == BO_LAnd || Opcode == BO_LOr) &&
1192  areEquivalentRanges(LhsOpcode, LhsValue, RhsOpcode, RhsValue)) {
1193  diag(ComparisonOperator->getOperatorLoc(),
1194  "equivalent expression on both sides of logical operator");
1195  return;
1196  }
1197 
1198  if (Opcode == BO_LAnd) {
1199  if (areExclusiveRanges(LhsOpcode, LhsValue, RhsOpcode, RhsValue)) {
1200  diag(ComparisonOperator->getOperatorLoc(),
1201  "logical expression is always false");
1202  } else if (rangeSubsumesRange(LhsOpcode, LhsValue, RhsOpcode, RhsValue)) {
1203  diag(LhsExpr->getExprLoc(), "expression is redundant");
1204  } else if (rangeSubsumesRange(RhsOpcode, RhsValue, LhsOpcode, LhsValue)) {
1205  diag(RhsExpr->getExprLoc(), "expression is redundant");
1206  }
1207  }
1208 
1209  if (Opcode == BO_LOr) {
1210  if (rangesFullyCoverDomain(LhsOpcode, LhsValue, RhsOpcode, RhsValue)) {
1211  diag(ComparisonOperator->getOperatorLoc(),
1212  "logical expression is always true");
1213  } else if (rangeSubsumesRange(LhsOpcode, LhsValue, RhsOpcode, RhsValue)) {
1214  diag(RhsExpr->getExprLoc(), "expression is redundant");
1215  } else if (rangeSubsumesRange(RhsOpcode, RhsValue, LhsOpcode, LhsValue)) {
1216  diag(LhsExpr->getExprLoc(), "expression is redundant");
1217  }
1218  }
1219  }
1220 }
1221 
1222 void RedundantExpressionCheck::check(const MatchFinder::MatchResult &Result) {
1223  if (const auto *BinOp = Result.Nodes.getNodeAs<BinaryOperator>("binary")) {
1224  // If the expression's constants are macros, check whether they are
1225  // intentional.
1226  if (areSidesBinaryConstExpressions(BinOp, Result.Context)) {
1227  const Expr *LhsConst = nullptr, *RhsConst = nullptr;
1228  BinaryOperatorKind MainOpcode, SideOpcode;
1229 
1230  if (!retrieveConstExprFromBothSides(BinOp, MainOpcode, SideOpcode,
1231  LhsConst, RhsConst, Result.Context))
1232  return;
1233 
1234  if (areExprsFromDifferentMacros(LhsConst, RhsConst, Result.Context) ||
1235  areExprsMacroAndNonMacro(LhsConst, RhsConst))
1236  return;
1237  }
1238 
1239  diag(BinOp->getOperatorLoc(), "both sides of operator are equivalent");
1240  }
1241 
1242  if (const auto *CondOp =
1243  Result.Nodes.getNodeAs<ConditionalOperator>("cond")) {
1244  const Expr *TrueExpr = CondOp->getTrueExpr();
1245  const Expr *FalseExpr = CondOp->getFalseExpr();
1246 
1247  if (areExprsFromDifferentMacros(TrueExpr, FalseExpr, Result.Context) ||
1248  areExprsMacroAndNonMacro(TrueExpr, FalseExpr))
1249  return;
1250  diag(CondOp->getColonLoc(),
1251  "'true' and 'false' expressions are equivalent");
1252  }
1253 
1254  if (const auto *Call = Result.Nodes.getNodeAs<CXXOperatorCallExpr>("call")) {
1255  if (canOverloadedOperatorArgsBeModified(Call, true))
1256  return;
1257 
1258  diag(Call->getOperatorLoc(),
1259  "both sides of overloaded operator are equivalent");
1260  }
1261 
1262  if (const auto *Op = Result.Nodes.getNodeAs<Expr>("nested-duplicates")) {
1263  const auto *Call = dyn_cast<CXXOperatorCallExpr>(Op);
1264  if (Call && canOverloadedOperatorArgsBeModified(Call, true))
1265  return;
1266 
1267  StringRef Message =
1268  Call ? "overloaded operator has equivalent nested operands"
1269  : "operator has equivalent nested operands";
1270 
1271  const auto Diag = diag(Op->getExprLoc(), Message);
1272  for (const auto &KeyValue : Result.Nodes.getMap()) {
1273  if (StringRef(KeyValue.first).startswith("duplicate"))
1274  Diag << KeyValue.second.getSourceRange();
1275  }
1276  }
1277 
1278  if (const auto *NegateOperator =
1279  Result.Nodes.getNodeAs<UnaryOperator>("logical-bitwise-confusion")) {
1280  SourceLocation OperatorLoc = NegateOperator->getOperatorLoc();
1281 
1282  auto Diag =
1283  diag(OperatorLoc,
1284  "ineffective logical negation operator used; did you mean '~'?");
1285  SourceLocation LogicalNotLocation = OperatorLoc.getLocWithOffset(1);
1286 
1287  if (!LogicalNotLocation.isMacroID())
1288  Diag << FixItHint::CreateReplacement(
1289  CharSourceRange::getCharRange(OperatorLoc, LogicalNotLocation), "~");
1290  }
1291 
1292  if (const auto *BinaryAndExpr = Result.Nodes.getNodeAs<BinaryOperator>(
1293  "left-right-shift-confusion")) {
1294  const auto *ShiftingConst = Result.Nodes.getNodeAs<Expr>("shift-const");
1295  assert(ShiftingConst && "Expr* 'ShiftingConst' is nullptr!");
1296  Optional<llvm::APSInt> ShiftingValue =
1297  ShiftingConst->getIntegerConstantExpr(*Result.Context);
1298 
1299  if (!ShiftingValue)
1300  return;
1301 
1302  const auto *AndConst = Result.Nodes.getNodeAs<Expr>("and-const");
1303  assert(AndConst && "Expr* 'AndCont' is nullptr!");
1304  Optional<llvm::APSInt> AndValue =
1305  AndConst->getIntegerConstantExpr(*Result.Context);
1306  if (!AndValue)
1307  return;
1308 
1309  // If ShiftingConst is shifted left with more bits than the position of the
1310  // leftmost 1 in the bit representation of AndValue, AndConstant is
1311  // ineffective.
1312  if (AndValue->getActiveBits() > *ShiftingValue)
1313  return;
1314 
1315  auto Diag = diag(BinaryAndExpr->getOperatorLoc(),
1316  "ineffective bitwise and operation");
1317  }
1318 
1319  // Check for the following bound expressions:
1320  // - "binop-const-compare-to-sym",
1321  // - "binop-const-compare-to-binop-const",
1322  // Produced message:
1323  // -> "logical expression is always false/true"
1324  checkArithmeticExpr(Result);
1325 
1326  // Check for the following bound expression:
1327  // - "binop-const-compare-to-const",
1328  // - "ineffective-bitwise"
1329  // Produced message:
1330  // -> "logical expression is always false/true"
1331  // -> "expression always evaluates to ..."
1332  checkBitwiseExpr(Result);
1333 
1334  // Check for te following bound expression:
1335  // - "comparisons-of-symbol-and-const",
1336  // Produced messages:
1337  // -> "equivalent expression on both sides of logical operator",
1338  // -> "logical expression is always false/true"
1339  // -> "expression is redundant"
1340  checkRelationalExpr(Result);
1341 }
1342 
1343 } // namespace misc
1344 } // namespace tidy
1345 } // namespace clang
Loc
SourceLocation Loc
Definition: KernelNameRestrictionCheck.cpp:45
clang::tidy::misc::exprEvaluatesToBitwiseNegatedZero
static bool exprEvaluatesToBitwiseNegatedZero(BinaryOperatorKind Opcode, APSInt Value)
Definition: RedundantExpressionCheck.cpp:1073
clang::tidy::utils::fixit::QualifierPolicy::Right
@ Right
E
const Expr * E
Definition: AvoidBindCheck.cpp:88
clang::clangd::check
bool check(llvm::StringRef File, llvm::Optional< Range > LineRange, const ThreadsafeFS &TFS, const ClangdLSPServer::Options &Opts, bool EnableCodeCompletion)
Definition: Check.cpp:273
clang::tidy::misc::exprEvaluatesToSymbolic
static bool exprEvaluatesToSymbolic(BinaryOperatorKind Opcode, APSInt Value)
Definition: RedundantExpressionCheck.cpp:1078
clang::clangd::TypeHierarchyDirection::Parents
@ Parents
clang::tidy::bugprone::Message
static const char Message[]
Definition: ReservedIdentifierCheck.cpp:31
clang::tidy::cppcoreguidelines::getSourceText
static std::string getSourceText(const CXXDestructorDecl &Destructor)
Definition: VirtualClassDestructorCheck.cpp:112
clang::tidy::matchers
Definition: clang-tidy/utils/Matchers.h:17
clang::ast_matchers
Definition: AbseilMatcher.h:14
clang::tidy::abseil::getValue
static double getValue(const IntegerLiteral *IntLit, const FloatingLiteral *FloatLit)
Definition: DurationFactoryScaleCheck.cpp:38
clang::tidy::utils::fixit::QualifierPolicy::Left
@ Left
Builder
CodeCompletionBuilder Builder
Definition: CodeCompletionStringsTests.cpp:36
clang::ast_matchers::AST_MATCHER
AST_MATCHER(Expr, isMacroID)
Definition: PreferIsaOrDynCastInConditionalsCheck.cpp:19
Parent
const Node * Parent
Definition: ExtractFunction.cpp:157
clang
===– Representation.cpp - ClangDoc Representation --------—*- C++ -*-===//
Definition: ApplyReplacements.h:27
clang::tidy::misc::exprEvaluatesToZero
static bool exprEvaluatesToZero(BinaryOperatorKind Opcode, APSInt Value)
Definition: RedundantExpressionCheck.cpp:1069
RedundantExpressionCheck.h
clang::tidy::bugprone::AST_MATCHER_P
AST_MATCHER_P(FunctionDecl, parameterCountGE, unsigned, N)
Matches functions that have at least the specified amount of parameters.
Definition: EasilySwappableParametersCheck.cpp:1888