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