contrib/llvm/tools/clang/lib/StaticAnalyzer/Checkers/IdenticalExprChecker.cpp

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