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