clang/lib/StaticAnalyzer/Checkers/IdenticalExprChecker.cpp

   1 //== IdenticalExprChecker.cpp - Identical expression checker----------------==//
   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 ///
   9 /// \file
  10 /// This defines IdenticalExprChecker, a check that warns about
  11 /// unintended use of identical expressions.
  12 ///
  13 /// It checks for use of identical expressions with comparison operators and
  14 /// inside conditional expressions.
  15 ///
  16 //===----------------------------------------------------------------------===//
  17
  18 #include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"
  19 #include "clang/AST/RecursiveASTVisitor.h"
  20 #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
  21 #include "clang/StaticAnalyzer/Core/Checker.h"
  22 #include "clang/StaticAnalyzer/Core/CheckerManager.h"
  23 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
  24
  25 using namespace clang;
  26 using namespace ento;
  27
  28 static bool isIdenticalStmt(const ASTContext &Ctx, const Stmt *Stmt1,
  29                             const Stmt *Stmt2, bool IgnoreSideEffects = false);
  30 //===----------------------------------------------------------------------===//
  31 // FindIdenticalExprVisitor - Identify nodes using identical expressions.
  32 //===----------------------------------------------------------------------===//
  33
  34 namespace {
  35 class FindIdenticalExprVisitor
  36     : public RecursiveASTVisitor<FindIdenticalExprVisitor> {
  37   BugReporter &BR;
  38   const CheckerBase *Checker;
  39   AnalysisDeclContext *AC;
  40 public:
  41   explicit FindIdenticalExprVisitor(BugReporter &B,
  42                                     const CheckerBase *Checker,
  43                                     AnalysisDeclContext *A)
  44       : BR(B), Checker(Checker), AC(A) {}
  45   // FindIdenticalExprVisitor only visits nodes
  46   // that are binary operators, if statements or
  47   // conditional operators.
  48   bool VisitBinaryOperator(const BinaryOperator *B);
  49   bool VisitIfStmt(const IfStmt *I);
  50   bool VisitConditionalOperator(const ConditionalOperator *C);
  51
  52 private:
  53   void reportIdenticalExpr(const BinaryOperator *B, bool CheckBitwise,
  54                            ArrayRef<SourceRange> Sr);
  55   void checkBitwiseOrLogicalOp(const BinaryOperator *B, bool CheckBitwise);
  56   void checkComparisonOp(const BinaryOperator *B);
  57 };
  58 } // end anonymous namespace
  59
  60 void FindIdenticalExprVisitor::reportIdenticalExpr(const BinaryOperator *B,
  61                                                    bool CheckBitwise,
  62                                                    ArrayRef<SourceRange> Sr) {
  63   StringRef Message;
  64   if (CheckBitwise)
  65     Message = "identical expressions on both sides of bitwise operator";
  66   else
  67     Message = "identical expressions on both sides of logical operator";
  68
  69   PathDiagnosticLocation ELoc =
  70       PathDiagnosticLocation::createOperatorLoc(B, BR.getSourceManager());
  71   BR.EmitBasicReport(AC->getDecl(), Checker,
  72                      "Use of identical expressions",
  73                      categories::LogicError,
  74                      Message, ELoc, Sr);
  75 }
  76
  77 void FindIdenticalExprVisitor::checkBitwiseOrLogicalOp(const BinaryOperator *B,
  78                                                        bool CheckBitwise) {
  79   SourceRange Sr[2];
  80
  81   const Expr *LHS = B->getLHS();
  82   const Expr *RHS = B->getRHS();
  83
  84   // Split operators as long as we still have operators to split on. We will
  85   // get called for every binary operator in an expression so there is no need
  86   // to check every one against each other here, just the right most one with
  87   // the others.
  88   while (const BinaryOperator *B2 = dyn_cast<BinaryOperator>(LHS)) {
  89     if (B->getOpcode() != B2->getOpcode())
  90       break;
  91     if (isIdenticalStmt(AC->getASTContext(), RHS, B2->getRHS())) {
  92       Sr[0] = RHS->getSourceRange();
  93       Sr[1] = B2->getRHS()->getSourceRange();
  94       reportIdenticalExpr(B, CheckBitwise, Sr);
  95     }
  96     LHS = B2->getLHS();
  97   }
  98
  99   if (isIdenticalStmt(AC->getASTContext(), RHS, LHS)) {
 100     Sr[0] = RHS->getSourceRange();
 101     Sr[1] = LHS->getSourceRange();
 102     reportIdenticalExpr(B, CheckBitwise, Sr);
 103   }
 104 }
 105
 106 bool FindIdenticalExprVisitor::VisitIfStmt(const IfStmt *I) {
 107   const Stmt *Stmt1 = I->getThen();
 108   const Stmt *Stmt2 = I->getElse();
 109
 110   // Check for identical inner condition:
 111   //
 112   // if (x<10) {
 113   //   if (x<10) {
 114   //   ..
 115   if (const CompoundStmt *CS = dyn_cast<CompoundStmt>(Stmt1)) {
 116     if (!CS->body_empty()) {
 117       const IfStmt *InnerIf = dyn_cast<IfStmt>(*CS->body_begin());
 118       if (InnerIf && isIdenticalStmt(AC->getASTContext(), I->getCond(), InnerIf->getCond(), /*IgnoreSideEffects=*/ false)) {
 119         PathDiagnosticLocation ELoc(InnerIf->getCond(), BR.getSourceManager(), AC);
 120         BR.EmitBasicReport(AC->getDecl(), Checker, "Identical conditions",
 121           categories::LogicError,
 122           "conditions of the inner and outer statements are identical",
 123           ELoc);
 124       }
 125     }
 126   }
 127
 128   // Check for identical conditions:
 129   //
 130   // if (b) {
 131   //   foo1();
 132   // } else if (b) {
 133   //   foo2();
 134   // }
 135   if (Stmt1 && Stmt2) {
 136     const Expr *Cond1 = I->getCond();
 137     const Stmt *Else = Stmt2;
 138     while (const IfStmt *I2 = dyn_cast_or_null<IfStmt>(Else)) {
 139       const Expr *Cond2 = I2->getCond();
 140       if (isIdenticalStmt(AC->getASTContext(), Cond1, Cond2, false)) {
 141         SourceRange Sr = Cond1->getSourceRange();
 142         PathDiagnosticLocation ELoc(Cond2, BR.getSourceManager(), AC);
 143         BR.EmitBasicReport(AC->getDecl(), Checker, "Identical conditions",
 144                            categories::LogicError,
 145                            "expression is identical to previous condition",
 146                            ELoc, Sr);
 147       }
 148       Else = I2->getElse();
 149     }
 150   }
 151
 152   if (!Stmt1 || !Stmt2)
 153     return true;
 154
 155   // Special handling for code like:
 156   //
 157   // if (b) {
 158   //   i = 1;
 159   // } else
 160   //   i = 1;
 161   if (const CompoundStmt *CompStmt = dyn_cast<CompoundStmt>(Stmt1)) {
 162     if (CompStmt->size() == 1)
 163       Stmt1 = CompStmt->body_back();
 164   }
 165   if (const CompoundStmt *CompStmt = dyn_cast<CompoundStmt>(Stmt2)) {
 166     if (CompStmt->size() == 1)
 167       Stmt2 = CompStmt->body_back();
 168   }
 169
 170   if (isIdenticalStmt(AC->getASTContext(), Stmt1, Stmt2, true)) {
 171       PathDiagnosticLocation ELoc =
 172           PathDiagnosticLocation::createBegin(I, BR.getSourceManager(), AC);
 173       BR.EmitBasicReport(AC->getDecl(), Checker,
 174                          "Identical branches",
 175                          categories::LogicError,
 176                          "true and false branches are identical", ELoc);
 177   }
 178   return true;
 179 }
 180
 181 bool FindIdenticalExprVisitor::VisitBinaryOperator(const BinaryOperator *B) {
 182   BinaryOperator::Opcode Op = B->getOpcode();
 183
 184   if (BinaryOperator::isBitwiseOp(Op))
 185     checkBitwiseOrLogicalOp(B, true);
 186
 187   if (BinaryOperator::isLogicalOp(Op))
 188     checkBitwiseOrLogicalOp(B, false);
 189
 190   if (BinaryOperator::isComparisonOp(Op))
 191     checkComparisonOp(B);
 192
 193   // We want to visit ALL nodes (subexpressions of binary comparison
 194   // expressions too) that contains comparison operators.
 195   // True is always returned to traverse ALL nodes.
 196   return true;
 197 }
 198
 199 void FindIdenticalExprVisitor::checkComparisonOp(const BinaryOperator *B) {
 200   BinaryOperator::Opcode Op = B->getOpcode();
 201
 202   //
 203   // Special case for floating-point representation.
 204   //
 205   // If expressions on both sides of comparison operator are of type float,
 206   // then for some comparison operators no warning shall be
 207   // reported even if the expressions are identical from a symbolic point of
 208   // view. Comparison between expressions, declared variables and literals
 209   // are treated differently.
 210   //
 211   // != and == between float literals that have the same value should NOT warn.
 212   // < > between float literals that have the same value SHOULD warn.
 213   //
 214   // != and == between the same float declaration should NOT warn.
 215   // < > between the same float declaration SHOULD warn.
 216   //
 217   // != and == between eq. expressions that evaluates into float
 218   //           should NOT warn.
 219   // < >       between eq. expressions that evaluates into float
 220   //           should NOT warn.
 221   //
 222   const Expr *LHS = B->getLHS()->IgnoreParenImpCasts();
 223   const Expr *RHS = B->getRHS()->IgnoreParenImpCasts();
 224
 225   const DeclRefExpr *DeclRef1 = dyn_cast<DeclRefExpr>(LHS);
 226   const DeclRefExpr *DeclRef2 = dyn_cast<DeclRefExpr>(RHS);
 227   const FloatingLiteral *FloatLit1 = dyn_cast<FloatingLiteral>(LHS);
 228   const FloatingLiteral *FloatLit2 = dyn_cast<FloatingLiteral>(RHS);
 229   if ((DeclRef1) && (DeclRef2)) {
 230     if ((DeclRef1->getType()->hasFloatingRepresentation()) &&
 231         (DeclRef2->getType()->hasFloatingRepresentation())) {
 232       if (DeclRef1->getDecl() == DeclRef2->getDecl()) {
 233         if ((Op == BO_EQ) || (Op == BO_NE)) {
 234           return;
 235         }
 236       }
 237     }
 238   } else if ((FloatLit1) && (FloatLit2)) {
 239     if (FloatLit1->getValue().bitwiseIsEqual(FloatLit2->getValue())) {
 240       if ((Op == BO_EQ) || (Op == BO_NE)) {
 241         return;
 242       }
 243     }
 244   } else if (LHS->getType()->hasFloatingRepresentation()) {
 245     // If any side of comparison operator still has floating-point
 246     // representation, then it's an expression. Don't warn.
 247     // Here only LHS is checked since RHS will be implicit casted to float.
 248     return;
 249   } else {
 250     // No special case with floating-point representation, report as usual.
 251   }
 252
 253   if (isIdenticalStmt(AC->getASTContext(), B->getLHS(), B->getRHS())) {
 254     PathDiagnosticLocation ELoc =
 255         PathDiagnosticLocation::createOperatorLoc(B, BR.getSourceManager());
 256     StringRef Message;
 257     if (Op == BO_Cmp)
 258       Message = "comparison of identical expressions always evaluates to "
 259                 "'equal'";
 260     else if (((Op == BO_EQ) || (Op == BO_LE) || (Op == BO_GE)))
 261       Message = "comparison of identical expressions always evaluates to true";
 262     else
 263       Message = "comparison of identical expressions always evaluates to false";
 264     BR.EmitBasicReport(AC->getDecl(), Checker,
 265                        "Compare of identical expressions",
 266                        categories::LogicError, Message, ELoc);
 267   }
 268 }
 269
 270 bool FindIdenticalExprVisitor::VisitConditionalOperator(
 271     const ConditionalOperator *C) {
 272
 273   // Check if expressions in conditional expression are identical
 274   // from a symbolic point of view.
 275
 276   if (isIdenticalStmt(AC->getASTContext(), C->getTrueExpr(),
 277                       C->getFalseExpr(), true)) {
 278     PathDiagnosticLocation ELoc =
 279         PathDiagnosticLocation::createConditionalColonLoc(
 280             C, BR.getSourceManager());
 281
 282     SourceRange Sr[2];
 283     Sr[0] = C->getTrueExpr()->getSourceRange();
 284     Sr[1] = C->getFalseExpr()->getSourceRange();
 285     BR.EmitBasicReport(
 286         AC->getDecl(), Checker,
 287         "Identical expressions in conditional expression",
 288         categories::LogicError,
 289         "identical expressions on both sides of ':' in conditional expression",
 290         ELoc, Sr);
 291   }
 292   // We want to visit ALL nodes (expressions in conditional
 293   // expressions too) that contains conditional operators,
 294   // thus always return true to traverse ALL nodes.
 295   return true;
 296 }
 297
 298 /// Determines whether two statement trees are identical regarding
 299 /// operators and symbols.
 300 ///
 301 /// Exceptions: expressions containing macros or functions with possible side
 302 /// effects are never considered identical.
 303 /// Limitations: (t + u) and (u + t) are not considered identical.
 304 /// t*(u + t) and t*u + t*t are not considered identical.
 305 ///
 306 static bool isIdenticalStmt(const ASTContext &Ctx, const Stmt *Stmt1,
 307                             const Stmt *Stmt2, bool IgnoreSideEffects) {
 308
 309   if (!Stmt1 || !Stmt2) {
 310     return !Stmt1 && !Stmt2;
 311   }
 312
 313   // If Stmt1 & Stmt2 are of different class then they are not
 314   // identical statements.
 315   if (Stmt1->getStmtClass() != Stmt2->getStmtClass())
 316     return false;
 317
 318   const Expr *Expr1 = dyn_cast<Expr>(Stmt1);
 319   const Expr *Expr2 = dyn_cast<Expr>(Stmt2);
 320
 321   if (Expr1 && Expr2) {
 322     // If Stmt1 has side effects then don't warn even if expressions
 323     // are identical.
 324     if (!IgnoreSideEffects && Expr1->HasSideEffects(Ctx))
 325       return false;
 326     // If either expression comes from a macro then don't warn even if
 327     // the expressions are identical.
 328     if ((Expr1->getExprLoc().isMacroID()) || (Expr2->getExprLoc().isMacroID()))
 329       return false;
 330
 331     // If all children of two expressions are identical, return true.
 332     Expr::const_child_iterator I1 = Expr1->child_begin();
 333     Expr::const_child_iterator I2 = Expr2->child_begin();
 334     while (I1 != Expr1->child_end() && I2 != Expr2->child_end()) {
 335       if (!*I1 || !*I2 || !isIdenticalStmt(Ctx, *I1, *I2, IgnoreSideEffects))
 336         return false;
 337       ++I1;
 338       ++I2;
 339     }
 340     // If there are different number of children in the statements, return
 341     // false.
 342     if (I1 != Expr1->child_end())
 343       return false;
 344     if (I2 != Expr2->child_end())
 345       return false;
 346   }
 347
 348   switch (Stmt1->getStmtClass()) {
 349   default:
 350     return false;
 351   case Stmt::CallExprClass:
 352   case Stmt::ArraySubscriptExprClass:
 353   case Stmt::OMPArraySectionExprClass:
 354   case Stmt::OMPArrayShapingExprClass:
 355   case Stmt::OMPIteratorExprClass:
 356   case Stmt::ImplicitCastExprClass:
 357   case Stmt::ParenExprClass:
 358   case Stmt::BreakStmtClass:
 359   case Stmt::ContinueStmtClass:
 360   case Stmt::NullStmtClass:
 361     return true;
 362   case Stmt::CStyleCastExprClass: {
 363     const CStyleCastExpr* CastExpr1 = cast<CStyleCastExpr>(Stmt1);
 364     const CStyleCastExpr* CastExpr2 = cast<CStyleCastExpr>(Stmt2);
 365
 366     return CastExpr1->getTypeAsWritten() == CastExpr2->getTypeAsWritten();
 367   }
 368   case Stmt::ReturnStmtClass: {
 369     const ReturnStmt *ReturnStmt1 = cast<ReturnStmt>(Stmt1);
 370     const ReturnStmt *ReturnStmt2 = cast<ReturnStmt>(Stmt2);
 371
 372     return isIdenticalStmt(Ctx, ReturnStmt1->getRetValue(),
 373                            ReturnStmt2->getRetValue(), IgnoreSideEffects);
 374   }
 375   case Stmt::ForStmtClass: {
 376     const ForStmt *ForStmt1 = cast<ForStmt>(Stmt1);
 377     const ForStmt *ForStmt2 = cast<ForStmt>(Stmt2);
 378
 379     if (!isIdenticalStmt(Ctx, ForStmt1->getInit(), ForStmt2->getInit(),
 380                          IgnoreSideEffects))
 381       return false;
 382     if (!isIdenticalStmt(Ctx, ForStmt1->getCond(), ForStmt2->getCond(),
 383                          IgnoreSideEffects))
 384       return false;
 385     if (!isIdenticalStmt(Ctx, ForStmt1->getInc(), ForStmt2->getInc(),
 386                          IgnoreSideEffects))
 387       return false;
 388     if (!isIdenticalStmt(Ctx, ForStmt1->getBody(), ForStmt2->getBody(),
 389                          IgnoreSideEffects))
 390       return false;
 391     return true;
 392   }
 393   case Stmt::DoStmtClass: {
 394     const DoStmt *DStmt1 = cast<DoStmt>(Stmt1);
 395     const DoStmt *DStmt2 = cast<DoStmt>(Stmt2);
 396
 397     if (!isIdenticalStmt(Ctx, DStmt1->getCond(), DStmt2->getCond(),
 398                          IgnoreSideEffects))
 399       return false;
 400     if (!isIdenticalStmt(Ctx, DStmt1->getBody(), DStmt2->getBody(),
 401                          IgnoreSideEffects))
 402       return false;
 403     return true;
 404   }
 405   case Stmt::WhileStmtClass: {
 406     const WhileStmt *WStmt1 = cast<WhileStmt>(Stmt1);
 407     const WhileStmt *WStmt2 = cast<WhileStmt>(Stmt2);
 408
 409     if (!isIdenticalStmt(Ctx, WStmt1->getCond(), WStmt2->getCond(),
 410                          IgnoreSideEffects))
 411       return false;
 412     if (!isIdenticalStmt(Ctx, WStmt1->getBody(), WStmt2->getBody(),
 413                          IgnoreSideEffects))
 414       return false;
 415     return true;
 416   }
 417   case Stmt::IfStmtClass: {
 418     const IfStmt *IStmt1 = cast<IfStmt>(Stmt1);
 419     const IfStmt *IStmt2 = cast<IfStmt>(Stmt2);
 420
 421     if (!isIdenticalStmt(Ctx, IStmt1->getCond(), IStmt2->getCond(),
 422                          IgnoreSideEffects))
 423       return false;
 424     if (!isIdenticalStmt(Ctx, IStmt1->getThen(), IStmt2->getThen(),
 425                          IgnoreSideEffects))
 426       return false;
 427     if (!isIdenticalStmt(Ctx, IStmt1->getElse(), IStmt2->getElse(),
 428                          IgnoreSideEffects))
 429       return false;
 430     return true;
 431   }
 432   case Stmt::CompoundStmtClass: {
 433     const CompoundStmt *CompStmt1 = cast<CompoundStmt>(Stmt1);
 434     const CompoundStmt *CompStmt2 = cast<CompoundStmt>(Stmt2);
 435
 436     if (CompStmt1->size() != CompStmt2->size())
 437       return false;
 438
 439     CompoundStmt::const_body_iterator I1 = CompStmt1->body_begin();
 440     CompoundStmt::const_body_iterator I2 = CompStmt2->body_begin();
 441     while (I1 != CompStmt1->body_end() && I2 != CompStmt2->body_end()) {
 442       if (!isIdenticalStmt(Ctx, *I1, *I2, IgnoreSideEffects))
 443         return false;
 444       ++I1;
 445       ++I2;
 446     }
 447
 448     return true;
 449   }
 450   case Stmt::CompoundAssignOperatorClass:
 451   case Stmt::BinaryOperatorClass: {
 452     const BinaryOperator *BinOp1 = cast<BinaryOperator>(Stmt1);
 453     const BinaryOperator *BinOp2 = cast<BinaryOperator>(Stmt2);
 454     return BinOp1->getOpcode() == BinOp2->getOpcode();
 455   }
 456   case Stmt::CharacterLiteralClass: {
 457     const CharacterLiteral *CharLit1 = cast<CharacterLiteral>(Stmt1);
 458     const CharacterLiteral *CharLit2 = cast<CharacterLiteral>(Stmt2);
 459     return CharLit1->getValue() == CharLit2->getValue();
 460   }
 461   case Stmt::DeclRefExprClass: {
 462     const DeclRefExpr *DeclRef1 = cast<DeclRefExpr>(Stmt1);
 463     const DeclRefExpr *DeclRef2 = cast<DeclRefExpr>(Stmt2);
 464     return DeclRef1->getDecl() == DeclRef2->getDecl();
 465   }
 466   case Stmt::IntegerLiteralClass: {
 467     const IntegerLiteral *IntLit1 = cast<IntegerLiteral>(Stmt1);
 468     const IntegerLiteral *IntLit2 = cast<IntegerLiteral>(Stmt2);
 469
 470     llvm::APInt I1 = IntLit1->getValue();
 471     llvm::APInt I2 = IntLit2->getValue();
 472     if (I1.getBitWidth() != I2.getBitWidth())
 473       return false;
 474     return  I1 == I2;
 475   }
 476   case Stmt::FloatingLiteralClass: {
 477     const FloatingLiteral *FloatLit1 = cast<FloatingLiteral>(Stmt1);
 478     const FloatingLiteral *FloatLit2 = cast<FloatingLiteral>(Stmt2);
 479     return FloatLit1->getValue().bitwiseIsEqual(FloatLit2->getValue());
 480   }
 481   case Stmt::StringLiteralClass: {
 482     const StringLiteral *StringLit1 = cast<StringLiteral>(Stmt1);
 483     const StringLiteral *StringLit2 = cast<StringLiteral>(Stmt2);
 484     return StringLit1->getBytes() == StringLit2->getBytes();
 485   }
 486   case Stmt::MemberExprClass: {
 487     const MemberExpr *MemberStmt1 = cast<MemberExpr>(Stmt1);
 488     const MemberExpr *MemberStmt2 = cast<MemberExpr>(Stmt2);
 489     return MemberStmt1->getMemberDecl() == MemberStmt2->getMemberDecl();
 490   }
 491   case Stmt::UnaryOperatorClass: {
 492     const UnaryOperator *UnaryOp1 = cast<UnaryOperator>(Stmt1);
 493     const UnaryOperator *UnaryOp2 = cast<UnaryOperator>(Stmt2);
 494     return UnaryOp1->getOpcode() == UnaryOp2->getOpcode();
 495   }
 496   }
 497 }
 498
 499 //===----------------------------------------------------------------------===//
 500 // FindIdenticalExprChecker
 501 //===----------------------------------------------------------------------===//
 502
 503 namespace {
 504 class FindIdenticalExprChecker : public Checker<check::ASTCodeBody> {
 505 public:
 506   void checkASTCodeBody(const Decl *D, AnalysisManager &Mgr,
 507                         BugReporter &BR) const {
 508     FindIdenticalExprVisitor Visitor(BR, this, Mgr.getAnalysisDeclContext(D));
 509     Visitor.TraverseDecl(const_cast<Decl *>(D));
 510   }
 511 };
 512 } // end anonymous namespace
 513
 514 void ento::registerIdenticalExprChecker(CheckerManager &Mgr) {
 515   Mgr.registerChecker<FindIdenticalExprChecker>();
 516 }
 517
 518 bool ento::shouldRegisterIdenticalExprChecker(const CheckerManager &mgr) {
 519   return true;
 520 }