contrib/llvm/tools/clang/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp

   1 // BugReporterVisitors.cpp - Helpers for reporting bugs -----------*- C++ -*--//
   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 //  This file defines a set of BugReporter "visitors" which can be used to
  11 //  enhance the diagnostics reported for a bug.
  12 //
  13 //===----------------------------------------------------------------------===//
  14 #include "clang/StaticAnalyzer/Core/BugReporter/BugReporterVisitor.h"
  15
  16 #include "clang/AST/Expr.h"
  17 #include "clang/AST/ExprObjC.h"
  18 #include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h"
  19 #include "clang/StaticAnalyzer/Core/BugReporter/PathDiagnostic.h"
  20 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
  21 #include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h"
  22 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
  23 #include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h"
  24 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
  25 #include "llvm/ADT/SmallString.h"
  26 #include "llvm/ADT/StringExtras.h"
  27
  28 using namespace clang;
  29 using namespace ento;
  30
  31 //===----------------------------------------------------------------------===//
  32 // Utility functions.
  33 //===----------------------------------------------------------------------===//
  34
  35 bool bugreporter::isDeclRefExprToReference(const Expr *E) {
  36   if (const DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(E)) {
  37     return DRE->getDecl()->getType()->isReferenceType();
  38   }
  39   return false;
  40 }
  41
  42 const Stmt *bugreporter::GetDerefExpr(const ExplodedNode *N) {
  43   // Pattern match for a few useful cases (do something smarter later):
  44   //   a[0], p->f, *p
  45   const PostStmt *Loc = N->getLocationAs<PostStmt>();
  46   if (!Loc)
  47     return 0;
  48
  49   const Expr *S = dyn_cast<Expr>(Loc->getStmt());
  50   if (!S)
  51     return 0;
  52   S = S->IgnoreParenCasts();
  53
  54   while (true) {
  55     if (const BinaryOperator *B = dyn_cast<BinaryOperator>(S)) {
  56       assert(B->isAssignmentOp());
  57       S = B->getLHS()->IgnoreParenCasts();
  58       continue;
  59     }
  60     else if (const UnaryOperator *U = dyn_cast<UnaryOperator>(S)) {
  61       if (U->getOpcode() == UO_Deref)
  62         return U->getSubExpr()->IgnoreParenCasts();
  63     }
  64     else if (const MemberExpr *ME = dyn_cast<MemberExpr>(S)) {
  65       if (ME->isArrow() || isDeclRefExprToReference(ME->getBase())) {
  66         return ME->getBase()->IgnoreParenCasts();
  67       }
  68     }
  69     else if (const ObjCIvarRefExpr *IvarRef = dyn_cast<ObjCIvarRefExpr>(S)) {
  70       return IvarRef->getBase()->IgnoreParenCasts();
  71     }
  72     else if (const ArraySubscriptExpr *AE = dyn_cast<ArraySubscriptExpr>(S)) {
  73       return AE->getBase();
  74     }
  75     break;
  76   }
  77
  78   return NULL;
  79 }
  80
  81 const Stmt *bugreporter::GetDenomExpr(const ExplodedNode *N) {
  82   const Stmt *S = N->getLocationAs<PreStmt>()->getStmt();
  83   if (const BinaryOperator *BE = dyn_cast<BinaryOperator>(S))
  84     return BE->getRHS();
  85   return NULL;
  86 }
  87
  88 const Stmt *bugreporter::GetRetValExpr(const ExplodedNode *N) {
  89   const Stmt *S = N->getLocationAs<PostStmt>()->getStmt();
  90   if (const ReturnStmt *RS = dyn_cast<ReturnStmt>(S))
  91     return RS->getRetValue();
  92   return NULL;
  93 }
  94
  95 //===----------------------------------------------------------------------===//
  96 // Definitions for bug reporter visitors.
  97 //===----------------------------------------------------------------------===//
  98
  99 PathDiagnosticPiece*
 100 BugReporterVisitor::getEndPath(BugReporterContext &BRC,
 101                                const ExplodedNode *EndPathNode,
 102                                BugReport &BR) {
 103   return 0;
 104 }
 105
 106 PathDiagnosticPiece*
 107 BugReporterVisitor::getDefaultEndPath(BugReporterContext &BRC,
 108                                       const ExplodedNode *EndPathNode,
 109                                       BugReport &BR) {
 110   PathDiagnosticLocation L =
 111     PathDiagnosticLocation::createEndOfPath(EndPathNode,BRC.getSourceManager());
 112
 113   BugReport::ranges_iterator Beg, End;
 114   llvm::tie(Beg, End) = BR.getRanges();
 115
 116   // Only add the statement itself as a range if we didn't specify any
 117   // special ranges for this report.
 118   PathDiagnosticPiece *P = new PathDiagnosticEventPiece(L,
 119       BR.getDescription(),
 120       Beg == End);
 121   for (; Beg != End; ++Beg)
 122     P->addRange(*Beg);
 123
 124   return P;
 125 }
 126
 127
 128 namespace {
 129 /// Emits an extra note at the return statement of an interesting stack frame.
 130 ///
 131 /// The returned value is marked as an interesting value, and if it's null,
 132 /// adds a visitor to track where it became null.
 133 ///
 134 /// This visitor is intended to be used when another visitor discovers that an
 135 /// interesting value comes from an inlined function call.
 136 class ReturnVisitor : public BugReporterVisitorImpl<ReturnVisitor> {
 137   const StackFrameContext *StackFrame;
 138   enum {
 139     Initial,
 140     MaybeSuppress,
 141     Satisfied
 142   } Mode;
 143
 144 public:
 145   ReturnVisitor(const StackFrameContext *Frame)
 146     : StackFrame(Frame), Mode(Initial) {}
 147
 148   static void *getTag() {
 149     static int Tag = 0;
 150     return static_cast<void *>(&Tag);
 151   }
 152
 153   virtual void Profile(llvm::FoldingSetNodeID &ID) const {
 154     ID.AddPointer(ReturnVisitor::getTag());
 155     ID.AddPointer(StackFrame);
 156   }
 157
 158   /// Adds a ReturnVisitor if the given statement represents a call that was
 159   /// inlined.
 160   ///
 161   /// This will search back through the ExplodedGraph, starting from the given
 162   /// node, looking for when the given statement was processed. If it turns out
 163   /// the statement is a call that was inlined, we add the visitor to the
 164   /// bug report, so it can print a note later.
 165   static void addVisitorIfNecessary(const ExplodedNode *Node, const Stmt *S,
 166                                     BugReport &BR) {
 167     if (!CallEvent::isCallStmt(S))
 168       return;
 169
 170     // First, find when we processed the statement.
 171     do {
 172       if (const CallExitEnd *CEE = Node->getLocationAs<CallExitEnd>())
 173         if (CEE->getCalleeContext()->getCallSite() == S)
 174           break;
 175       if (const StmtPoint *SP = Node->getLocationAs<StmtPoint>())
 176         if (SP->getStmt() == S)
 177           break;
 178
 179       Node = Node->getFirstPred();
 180     } while (Node);
 181
 182     // Next, step over any post-statement checks.
 183     while (Node && isa<PostStmt>(Node->getLocation()))
 184       Node = Node->getFirstPred();
 185
 186     // Finally, see if we inlined the call.
 187     if (Node) {
 188       if (const CallExitEnd *CEE = Node->getLocationAs<CallExitEnd>()) {
 189         const StackFrameContext *CalleeContext = CEE->getCalleeContext();
 190         if (CalleeContext->getCallSite() == S) {
 191           BR.markInteresting(CalleeContext);
 192           BR.addVisitor(new ReturnVisitor(CalleeContext));
 193         }
 194       }
 195     }
 196   }
 197
 198   /// Returns true if any counter-suppression heuristics are enabled for
 199   /// ReturnVisitor.
 200   static bool hasCounterSuppression(AnalyzerOptions &Options) {
 201     return Options.shouldAvoidSuppressingNullArgumentPaths();
 202   }
 203
 204   PathDiagnosticPiece *visitNodeInitial(const ExplodedNode *N,
 205                                         const ExplodedNode *PrevN,
 206                                         BugReporterContext &BRC,
 207                                         BugReport &BR) {
 208     // Only print a message at the interesting return statement.
 209     if (N->getLocationContext() != StackFrame)
 210       return 0;
 211
 212     const StmtPoint *SP = N->getLocationAs<StmtPoint>();
 213     if (!SP)
 214       return 0;
 215
 216     const ReturnStmt *Ret = dyn_cast<ReturnStmt>(SP->getStmt());
 217     if (!Ret)
 218       return 0;
 219
 220     // Okay, we're at the right return statement, but do we have the return
 221     // value available?
 222     ProgramStateRef State = N->getState();
 223     SVal V = State->getSVal(Ret, StackFrame);
 224     if (V.isUnknownOrUndef())
 225       return 0;
 226
 227     // Don't print any more notes after this one.
 228     Mode = Satisfied;
 229
 230     const Expr *RetE = Ret->getRetValue();
 231     assert(RetE && "Tracking a return value for a void function");
 232     RetE = RetE->IgnoreParenCasts();
 233
 234     // If we can't prove the return value is 0, just mark it interesting, and
 235     // make sure to track it into any further inner functions.
 236     if (State->assume(cast<DefinedSVal>(V), true)) {
 237       BR.markInteresting(V);
 238       ReturnVisitor::addVisitorIfNecessary(N, RetE, BR);
 239       return 0;
 240     }
 241
 242     // If we're returning 0, we should track where that 0 came from.
 243     bugreporter::trackNullOrUndefValue(N, RetE, BR);
 244
 245     // Build an appropriate message based on the return value.
 246     SmallString<64> Msg;
 247     llvm::raw_svector_ostream Out(Msg);
 248
 249     if (isa<Loc>(V)) {
 250       // If we are pruning null-return paths as unlikely error paths, mark the
 251       // report invalid. We still want to emit a path note, however, in case
 252       // the report is resurrected as valid later on.
 253       ExprEngine &Eng = BRC.getBugReporter().getEngine();
 254       AnalyzerOptions &Options = Eng.getAnalysisManager().options;
 255       if (Options.shouldPruneNullReturnPaths()) {
 256         if (hasCounterSuppression(Options))
 257           Mode = MaybeSuppress;
 258         else
 259           BR.markInvalid(ReturnVisitor::getTag(), StackFrame);
 260       }
 261
 262       if (RetE->getType()->isObjCObjectPointerType())
 263         Out << "Returning nil";
 264       else
 265         Out << "Returning null pointer";
 266     } else {
 267       Out << "Returning zero";
 268     }
 269
 270     // FIXME: We should have a more generalized location printing mechanism.
 271     if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(RetE))
 272       if (const DeclaratorDecl *DD = dyn_cast<DeclaratorDecl>(DR->getDecl()))
 273         Out << " (loaded from '" << *DD << "')";
 274
 275     PathDiagnosticLocation L(Ret, BRC.getSourceManager(), StackFrame);
 276     return new PathDiagnosticEventPiece(L, Out.str());
 277   }
 278
 279   PathDiagnosticPiece *visitNodeMaybeSuppress(const ExplodedNode *N,
 280                                               const ExplodedNode *PrevN,
 281                                               BugReporterContext &BRC,
 282                                               BugReport &BR) {
 283     // Are we at the entry node for this call?
 284     const CallEnter *CE = N->getLocationAs<CallEnter>();
 285     if (!CE)
 286       return 0;
 287
 288     if (CE->getCalleeContext() != StackFrame)
 289       return 0;
 290
 291     Mode = Satisfied;
 292
 293     ExprEngine &Eng = BRC.getBugReporter().getEngine();
 294     AnalyzerOptions &Options = Eng.getAnalysisManager().options;
 295     if (Options.shouldAvoidSuppressingNullArgumentPaths()) {
 296       // Don't automatically suppress a report if one of the arguments is
 297       // known to be a null pointer. Instead, start tracking /that/ null
 298       // value back to its origin.
 299       ProgramStateManager &StateMgr = BRC.getStateManager();
 300       CallEventManager &CallMgr = StateMgr.getCallEventManager();
 301
 302       ProgramStateRef State = N->getState();
 303       CallEventRef<> Call = CallMgr.getCaller(StackFrame, State);
 304       for (unsigned I = 0, E = Call->getNumArgs(); I != E; ++I) {
 305         SVal ArgV = Call->getArgSVal(I);
 306         if (!isa<Loc>(ArgV))
 307           continue;
 308
 309         const Expr *ArgE = Call->getArgExpr(I);
 310         if (!ArgE)
 311           continue;
 312
 313         // Is it possible for this argument to be non-null?
 314         if (State->assume(cast<Loc>(ArgV), true))
 315           continue;
 316
 317         if (bugreporter::trackNullOrUndefValue(N, ArgE, BR, /*IsArg=*/true))
 318           return 0;
 319
 320         // If we /can't/ track the null pointer, we should err on the side of
 321         // false negatives, and continue towards marking this report invalid.
 322         // (We will still look at the other arguments, though.)
 323       }
 324     }
 325
 326     // There is no reason not to suppress this report; go ahead and do it.
 327     BR.markInvalid(ReturnVisitor::getTag(), StackFrame);
 328     return 0;
 329   }
 330
 331   PathDiagnosticPiece *VisitNode(const ExplodedNode *N,
 332                                  const ExplodedNode *PrevN,
 333                                  BugReporterContext &BRC,
 334                                  BugReport &BR) {
 335     switch (Mode) {
 336     case Initial:
 337       return visitNodeInitial(N, PrevN, BRC, BR);
 338     case MaybeSuppress:
 339       return visitNodeMaybeSuppress(N, PrevN, BRC, BR);
 340     case Satisfied:
 341       return 0;
 342     }
 343
 344     llvm_unreachable("Invalid visit mode!");
 345   }
 346 };
 347 } // end anonymous namespace
 348
 349
 350 void FindLastStoreBRVisitor ::Profile(llvm::FoldingSetNodeID &ID) const {
 351   static int tag = 0;
 352   ID.AddPointer(&tag);
 353   ID.AddPointer(R);
 354   ID.Add(V);
 355 }
 356
 357 PathDiagnosticPiece *FindLastStoreBRVisitor::VisitNode(const ExplodedNode *Succ,
 358                                                        const ExplodedNode *Pred,
 359                                                        BugReporterContext &BRC,
 360                                                        BugReport &BR) {
 361
 362   if (satisfied)
 363     return NULL;
 364
 365   const ExplodedNode *StoreSite = 0;
 366   const Expr *InitE = 0;
 367   bool IsParam = false;
 368
 369   // First see if we reached the declaration of the region.
 370   if (const VarRegion *VR = dyn_cast<VarRegion>(R)) {
 371     if (const PostStmt *P = Pred->getLocationAs<PostStmt>()) {
 372       if (const DeclStmt *DS = P->getStmtAs<DeclStmt>()) {
 373         if (DS->getSingleDecl() == VR->getDecl()) {
 374           StoreSite = Pred;
 375           InitE = VR->getDecl()->getInit();
 376         }
 377       }
 378     }
 379   }
 380
 381   // Otherwise, check that Succ has this binding and Pred does not, i.e. this is
 382   // where the binding first occurred.
 383   if (!StoreSite) {
 384     if (Succ->getState()->getSVal(R) != V)
 385       return NULL;
 386     if (Pred->getState()->getSVal(R) == V)
 387       return NULL;
 388
 389     StoreSite = Succ;
 390
 391     // If this is an assignment expression, we can track the value
 392     // being assigned.
 393     if (const PostStmt *P = Succ->getLocationAs<PostStmt>())
 394       if (const BinaryOperator *BO = P->getStmtAs<BinaryOperator>())
 395         if (BO->isAssignmentOp())
 396           InitE = BO->getRHS();
 397
 398     // If this is a call entry, the variable should be a parameter.
 399     // FIXME: Handle CXXThisRegion as well. (This is not a priority because
 400     // 'this' should never be NULL, but this visitor isn't just for NULL and
 401     // UndefinedVal.)
 402     if (const CallEnter *CE = Succ->getLocationAs<CallEnter>()) {
 403       const VarRegion *VR = cast<VarRegion>(R);
 404       const ParmVarDecl *Param = cast<ParmVarDecl>(VR->getDecl());
 405
 406       ProgramStateManager &StateMgr = BRC.getStateManager();
 407       CallEventManager &CallMgr = StateMgr.getCallEventManager();
 408
 409       CallEventRef<> Call = CallMgr.getCaller(CE->getCalleeContext(),
 410                                               Succ->getState());
 411       InitE = Call->getArgExpr(Param->getFunctionScopeIndex());
 412       IsParam = true;
 413     }
 414   }
 415
 416   if (!StoreSite)
 417     return NULL;
 418   satisfied = true;
 419
 420   // If we have an expression that provided the value, try to track where it
 421   // came from.
 422   if (InitE) {
 423     if (V.isUndef() || isa<loc::ConcreteInt>(V)) {
 424       if (!IsParam)
 425         InitE = InitE->IgnoreParenCasts();
 426       bugreporter::trackNullOrUndefValue(StoreSite, InitE, BR, IsParam);
 427     } else {
 428       ReturnVisitor::addVisitorIfNecessary(StoreSite, InitE->IgnoreParenCasts(),
 429                                            BR);
 430     }
 431   }
 432
 433   if (!R->canPrintPretty())
 434     return 0;
 435
 436   // Okay, we've found the binding. Emit an appropriate message.
 437   SmallString<256> sbuf;
 438   llvm::raw_svector_ostream os(sbuf);
 439
 440   if (const PostStmt *PS = StoreSite->getLocationAs<PostStmt>()) {
 441     if (const DeclStmt *DS = PS->getStmtAs<DeclStmt>()) {
 442
 443       if (const VarRegion *VR = dyn_cast<VarRegion>(R)) {
 444         os << "Variable '" << *VR->getDecl() << "' ";
 445       }
 446       else
 447         return NULL;
 448
 449       if (isa<loc::ConcreteInt>(V)) {
 450         bool b = false;
 451         if (R->isBoundable()) {
 452           if (const TypedValueRegion *TR = dyn_cast<TypedValueRegion>(R)) {
 453             if (TR->getValueType()->isObjCObjectPointerType()) {
 454               os << "initialized to nil";
 455               b = true;
 456             }
 457           }
 458         }
 459
 460         if (!b)
 461           os << "initialized to a null pointer value";
 462       }
 463       else if (isa<nonloc::ConcreteInt>(V)) {
 464         os << "initialized to " << cast<nonloc::ConcreteInt>(V).getValue();
 465       }
 466       else if (V.isUndef()) {
 467         if (isa<VarRegion>(R)) {
 468           const VarDecl *VD = cast<VarDecl>(DS->getSingleDecl());
 469           if (VD->getInit())
 470             os << "initialized to a garbage value";
 471           else
 472             os << "declared without an initial value";
 473         }
 474       }
 475       else {
 476         os << "initialized here";
 477       }
 478     }
 479   } else if (isa<CallEnter>(StoreSite->getLocation())) {
 480     const ParmVarDecl *Param = cast<ParmVarDecl>(cast<VarRegion>(R)->getDecl());
 481
 482     os << "Passing ";
 483
 484     if (isa<loc::ConcreteInt>(V)) {
 485       if (Param->getType()->isObjCObjectPointerType())
 486         os << "nil object reference";
 487       else
 488         os << "null pointer value";
 489     } else if (V.isUndef()) {
 490       os << "uninitialized value";
 491     } else if (isa<nonloc::ConcreteInt>(V)) {
 492       os << "the value " << cast<nonloc::ConcreteInt>(V).getValue();
 493     } else {
 494       os << "value";
 495     }
 496
 497     // Printed parameter indexes are 1-based, not 0-based.
 498     unsigned Idx = Param->getFunctionScopeIndex() + 1;
 499     os << " via " << Idx << llvm::getOrdinalSuffix(Idx) << " parameter '";
 500
 501     R->printPretty(os);
 502     os << '\'';
 503   }
 504
 505   if (os.str().empty()) {
 506     if (isa<loc::ConcreteInt>(V)) {
 507       bool b = false;
 508       if (R->isBoundable()) {
 509         if (const TypedValueRegion *TR = dyn_cast<TypedValueRegion>(R)) {
 510           if (TR->getValueType()->isObjCObjectPointerType()) {
 511             os << "nil object reference stored to ";
 512             b = true;
 513           }
 514         }
 515       }
 516
 517       if (!b)
 518         os << "Null pointer value stored to ";
 519     }
 520     else if (V.isUndef()) {
 521       os << "Uninitialized value stored to ";
 522     }
 523     else if (isa<nonloc::ConcreteInt>(V)) {
 524       os << "The value " << cast<nonloc::ConcreteInt>(V).getValue()
 525                << " is assigned to ";
 526     }
 527     else
 528       os << "Value assigned to ";
 529
 530     os << '\'';
 531     R->printPretty(os);
 532     os << '\'';
 533   }
 534
 535   // Construct a new PathDiagnosticPiece.
 536   ProgramPoint P = StoreSite->getLocation();
 537   PathDiagnosticLocation L;
 538   if (isa<CallEnter>(P))
 539     L = PathDiagnosticLocation(InitE, BRC.getSourceManager(),
 540                                P.getLocationContext());
 541   else
 542     L = PathDiagnosticLocation::create(P, BRC.getSourceManager());
 543   if (!L.isValid())
 544     return NULL;
 545   return new PathDiagnosticEventPiece(L, os.str());
 546 }
 547
 548 void TrackConstraintBRVisitor::Profile(llvm::FoldingSetNodeID &ID) const {
 549   static int tag = 0;
 550   ID.AddPointer(&tag);
 551   ID.AddBoolean(Assumption);
 552   ID.Add(Constraint);
 553 }
 554
 555 /// Return the tag associated with this visitor.  This tag will be used
 556 /// to make all PathDiagnosticPieces created by this visitor.
 557 const char *TrackConstraintBRVisitor::getTag() {
 558   return "TrackConstraintBRVisitor";
 559 }
 560
 561 PathDiagnosticPiece *
 562 TrackConstraintBRVisitor::VisitNode(const ExplodedNode *N,
 563                                     const ExplodedNode *PrevN,
 564                                     BugReporterContext &BRC,
 565                                     BugReport &BR) {
 566   if (isSatisfied)
 567     return NULL;
 568
 569   // Check if in the previous state it was feasible for this constraint
 570   // to *not* be true.
 571   if (PrevN->getState()->assume(Constraint, !Assumption)) {
 572
 573     isSatisfied = true;
 574
 575     // As a sanity check, make sure that the negation of the constraint
 576     // was infeasible in the current state.  If it is feasible, we somehow
 577     // missed the transition point.
 578     if (N->getState()->assume(Constraint, !Assumption))
 579       return NULL;
 580
 581     // We found the transition point for the constraint.  We now need to
 582     // pretty-print the constraint. (work-in-progress)
 583     std::string sbuf;
 584     llvm::raw_string_ostream os(sbuf);
 585
 586     if (isa<Loc>(Constraint)) {
 587       os << "Assuming pointer value is ";
 588       os << (Assumption ? "non-null" : "null");
 589     }
 590
 591     if (os.str().empty())
 592       return NULL;
 593
 594     // Construct a new PathDiagnosticPiece.
 595     ProgramPoint P = N->getLocation();
 596     PathDiagnosticLocation L =
 597       PathDiagnosticLocation::create(P, BRC.getSourceManager());
 598     if (!L.isValid())
 599       return NULL;
 600
 601     PathDiagnosticEventPiece *X = new PathDiagnosticEventPiece(L, os.str());
 602     X->setTag(getTag());
 603     return X;
 604   }
 605
 606   return NULL;
 607 }
 608
 609 bool bugreporter::trackNullOrUndefValue(const ExplodedNode *N, const Stmt *S,
 610                                         BugReport &report, bool IsArg) {
 611   if (!S || !N)
 612     return false;
 613
 614   if (const OpaqueValueExpr *OVE = dyn_cast<OpaqueValueExpr>(S))
 615     S = OVE->getSourceExpr();
 616
 617   if (IsArg) {
 618     assert(isa<CallEnter>(N->getLocation()) && "Tracking arg but not at call");
 619   } else {
 620     // Walk through nodes until we get one that matches the statement exactly.
 621     do {
 622       const ProgramPoint &pp = N->getLocation();
 623       if (const PostStmt *ps = dyn_cast<PostStmt>(&pp)) {
 624         if (ps->getStmt() == S)
 625           break;
 626       } else if (const CallExitEnd *CEE = dyn_cast<CallExitEnd>(&pp)) {
 627         if (CEE->getCalleeContext()->getCallSite() == S)
 628           break;
 629       }
 630       N = N->getFirstPred();
 631     } while (N);
 632
 633     if (!N)
 634       return false;
 635   }
 636
 637   ProgramStateRef state = N->getState();
 638
 639   // See if the expression we're interested refers to a variable.
 640   // If so, we can track both its contents and constraints on its value.
 641   if (const Expr *Ex = dyn_cast<Expr>(S)) {
 642     // Strip off parens and casts. Note that this will never have issues with
 643     // C++ user-defined implicit conversions, because those have a constructor
 644     // or function call inside.
 645     Ex = Ex->IgnoreParenCasts();
 646     if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(Ex)) {
 647       // FIXME: Right now we only track VarDecls because it's non-trivial to
 648       // get a MemRegion for any other DeclRefExprs. <rdar://problem/12114812>
 649       if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) {
 650         ProgramStateManager &StateMgr = state->getStateManager();
 651         MemRegionManager &MRMgr = StateMgr.getRegionManager();
 652         const VarRegion *R = MRMgr.getVarRegion(VD, N->getLocationContext());
 653
 654         // Mark both the variable region and its contents as interesting.
 655         SVal V = state->getRawSVal(loc::MemRegionVal(R));
 656
 657         // If the value matches the default for the variable region, that
 658         // might mean that it's been cleared out of the state. Fall back to
 659         // the full argument expression (with casts and such intact).
 660         if (IsArg) {
 661           bool UseArgValue = V.isUnknownOrUndef() || V.isZeroConstant();
 662           if (!UseArgValue) {
 663             const SymbolRegionValue *SRV =
 664               dyn_cast_or_null<SymbolRegionValue>(V.getAsLocSymbol());
 665             if (SRV)
 666               UseArgValue = (SRV->getRegion() == R);
 667           }
 668           if (UseArgValue)
 669             V = state->getSValAsScalarOrLoc(S, N->getLocationContext());
 670         }
 671
 672         report.markInteresting(R);
 673         report.markInteresting(V);
 674         report.addVisitor(new UndefOrNullArgVisitor(R));
 675
 676         // If the contents are symbolic, find out when they became null.
 677         if (V.getAsLocSymbol()) {
 678           BugReporterVisitor *ConstraintTracker
 679             = new TrackConstraintBRVisitor(cast<DefinedSVal>(V), false);
 680           report.addVisitor(ConstraintTracker);
 681         }
 682
 683         report.addVisitor(new FindLastStoreBRVisitor(V, R));
 684         return true;
 685       }
 686     }
 687   }
 688
 689   // If the expression does NOT refer to a variable, we can still track
 690   // constraints on its contents.
 691   SVal V = state->getSValAsScalarOrLoc(S, N->getLocationContext());
 692
 693   // Uncomment this to find cases where we aren't properly getting the
 694   // base value that was dereferenced.
 695   // assert(!V.isUnknownOrUndef());
 696
 697   // Is it a symbolic value?
 698   if (loc::MemRegionVal *L = dyn_cast<loc::MemRegionVal>(&V)) {
 699     // At this point we are dealing with the region's LValue.
 700     // However, if the rvalue is a symbolic region, we should track it as well.
 701     SVal RVal = state->getSVal(L->getRegion());
 702     const MemRegion *RegionRVal = RVal.getAsRegion();
 703     report.addVisitor(new UndefOrNullArgVisitor(L->getRegion()));
 704
 705
 706     if (RegionRVal && isa<SymbolicRegion>(RegionRVal)) {
 707       report.markInteresting(RegionRVal);
 708       report.addVisitor(new TrackConstraintBRVisitor(
 709         loc::MemRegionVal(RegionRVal), false));
 710     }
 711   } else {
 712     // Otherwise, if the value came from an inlined function call,
 713     // we should at least make sure that function isn't pruned in our output.
 714     if (const Expr *E = dyn_cast<Expr>(S))
 715       S = E->IgnoreParenCasts();
 716     ReturnVisitor::addVisitorIfNecessary(N, S, report);
 717   }
 718
 719   return true;
 720 }
 721
 722 BugReporterVisitor *
 723 FindLastStoreBRVisitor::createVisitorObject(const ExplodedNode *N,
 724                                             const MemRegion *R) {
 725   assert(R && "The memory region is null.");
 726
 727   ProgramStateRef state = N->getState();
 728   SVal V = state->getSVal(R);
 729   if (V.isUnknown())
 730     return 0;
 731
 732   return new FindLastStoreBRVisitor(V, R);
 733 }
 734
 735
 736 PathDiagnosticPiece *NilReceiverBRVisitor::VisitNode(const ExplodedNode *N,
 737                                                      const ExplodedNode *PrevN,
 738                                                      BugReporterContext &BRC,
 739                                                      BugReport &BR) {
 740   const PostStmt *P = N->getLocationAs<PostStmt>();
 741   if (!P)
 742     return 0;
 743   const ObjCMessageExpr *ME = P->getStmtAs<ObjCMessageExpr>();
 744   if (!ME)
 745     return 0;
 746   const Expr *Receiver = ME->getInstanceReceiver();
 747   if (!Receiver)
 748     return 0;
 749   ProgramStateRef state = N->getState();
 750   const SVal &V = state->getSVal(Receiver, N->getLocationContext());
 751   const DefinedOrUnknownSVal *DV = dyn_cast<DefinedOrUnknownSVal>(&V);
 752   if (!DV)
 753     return 0;
 754   state = state->assume(*DV, true);
 755   if (state)
 756     return 0;
 757
 758   // The receiver was nil, and hence the method was skipped.
 759   // Register a BugReporterVisitor to issue a message telling us how
 760   // the receiver was null.
 761   bugreporter::trackNullOrUndefValue(N, Receiver, BR);
 762   // Issue a message saying that the method was skipped.
 763   PathDiagnosticLocation L(Receiver, BRC.getSourceManager(),
 764                                      N->getLocationContext());
 765   return new PathDiagnosticEventPiece(L, "No method is called "
 766       "because the receiver is nil");
 767 }
 768
 769 // Registers every VarDecl inside a Stmt with a last store visitor.
 770 void FindLastStoreBRVisitor::registerStatementVarDecls(BugReport &BR,
 771                                                        const Stmt *S) {
 772   const ExplodedNode *N = BR.getErrorNode();
 773   std::deque<const Stmt *> WorkList;
 774   WorkList.push_back(S);
 775
 776   while (!WorkList.empty()) {
 777     const Stmt *Head = WorkList.front();
 778     WorkList.pop_front();
 779
 780     ProgramStateRef state = N->getState();
 781     ProgramStateManager &StateMgr = state->getStateManager();
 782
 783     if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(Head)) {
 784       if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) {
 785         const VarRegion *R =
 786         StateMgr.getRegionManager().getVarRegion(VD, N->getLocationContext());
 787
 788         // What did we load?
 789         SVal V = state->getSVal(S, N->getLocationContext());
 790
 791         if (isa<loc::ConcreteInt>(V) || isa<nonloc::ConcreteInt>(V)) {
 792           // Register a new visitor with the BugReport.
 793           BR.addVisitor(new FindLastStoreBRVisitor(V, R));
 794         }
 795       }
 796     }
 797
 798     for (Stmt::const_child_iterator I = Head->child_begin();
 799         I != Head->child_end(); ++I)
 800       WorkList.push_back(*I);
 801   }
 802 }
 803
 804 //===----------------------------------------------------------------------===//
 805 // Visitor that tries to report interesting diagnostics from conditions.
 806 //===----------------------------------------------------------------------===//
 807
 808 /// Return the tag associated with this visitor.  This tag will be used
 809 /// to make all PathDiagnosticPieces created by this visitor.
 810 const char *ConditionBRVisitor::getTag() {
 811   return "ConditionBRVisitor";
 812 }
 813
 814 PathDiagnosticPiece *ConditionBRVisitor::VisitNode(const ExplodedNode *N,
 815                                                    const ExplodedNode *Prev,
 816                                                    BugReporterContext &BRC,
 817                                                    BugReport &BR) {
 818   PathDiagnosticPiece *piece = VisitNodeImpl(N, Prev, BRC, BR);
 819   if (piece) {
 820     piece->setTag(getTag());
 821     if (PathDiagnosticEventPiece *ev=dyn_cast<PathDiagnosticEventPiece>(piece))
 822       ev->setPrunable(true, /* override */ false);
 823   }
 824   return piece;
 825 }
 826
 827 PathDiagnosticPiece *ConditionBRVisitor::VisitNodeImpl(const ExplodedNode *N,
 828                                                        const ExplodedNode *Prev,
 829                                                        BugReporterContext &BRC,
 830                                                        BugReport &BR) {
 831
 832   ProgramPoint progPoint = N->getLocation();
 833   ProgramStateRef CurrentState = N->getState();
 834   ProgramStateRef PrevState = Prev->getState();
 835
 836   // Compare the GDMs of the state, because that is where constraints
 837   // are managed.  Note that ensure that we only look at nodes that
 838   // were generated by the analyzer engine proper, not checkers.
 839   if (CurrentState->getGDM().getRoot() ==
 840       PrevState->getGDM().getRoot())
 841     return 0;
 842
 843   // If an assumption was made on a branch, it should be caught
 844   // here by looking at the state transition.
 845   if (const BlockEdge *BE = dyn_cast<BlockEdge>(&progPoint)) {
 846     const CFGBlock *srcBlk = BE->getSrc();
 847     if (const Stmt *term = srcBlk->getTerminator())
 848       return VisitTerminator(term, N, srcBlk, BE->getDst(), BR, BRC);
 849     return 0;
 850   }
 851
 852   if (const PostStmt *PS = dyn_cast<PostStmt>(&progPoint)) {
 853     // FIXME: Assuming that BugReporter is a GRBugReporter is a layering
 854     // violation.
 855     const std::pair<const ProgramPointTag *, const ProgramPointTag *> &tags =
 856       cast<GRBugReporter>(BRC.getBugReporter()).
 857         getEngine().geteagerlyAssumeBinOpBifurcationTags();
 858
 859     const ProgramPointTag *tag = PS->getTag();
 860     if (tag == tags.first)
 861       return VisitTrueTest(cast<Expr>(PS->getStmt()), true,
 862                            BRC, BR, N);
 863     if (tag == tags.second)
 864       return VisitTrueTest(cast<Expr>(PS->getStmt()), false,
 865                            BRC, BR, N);
 866
 867     return 0;
 868   }
 869
 870   return 0;
 871 }
 872
 873 PathDiagnosticPiece *
 874 ConditionBRVisitor::VisitTerminator(const Stmt *Term,
 875                                     const ExplodedNode *N,
 876                                     const CFGBlock *srcBlk,
 877                                     const CFGBlock *dstBlk,
 878                                     BugReport &R,
 879                                     BugReporterContext &BRC) {
 880   const Expr *Cond = 0;
 881
 882   switch (Term->getStmtClass()) {
 883   default:
 884     return 0;
 885   case Stmt::IfStmtClass:
 886     Cond = cast<IfStmt>(Term)->getCond();
 887     break;
 888   case Stmt::ConditionalOperatorClass:
 889     Cond = cast<ConditionalOperator>(Term)->getCond();
 890     break;
 891   }
 892
 893   assert(Cond);
 894   assert(srcBlk->succ_size() == 2);
 895   const bool tookTrue = *(srcBlk->succ_begin()) == dstBlk;
 896   return VisitTrueTest(Cond, tookTrue, BRC, R, N);
 897 }
 898
 899 PathDiagnosticPiece *
 900 ConditionBRVisitor::VisitTrueTest(const Expr *Cond,
 901                                   bool tookTrue,
 902                                   BugReporterContext &BRC,
 903                                   BugReport &R,
 904                                   const ExplodedNode *N) {
 905
 906   const Expr *Ex = Cond;
 907
 908   while (true) {
 909     Ex = Ex->IgnoreParenCasts();
 910     switch (Ex->getStmtClass()) {
 911       default:
 912         return 0;
 913       case Stmt::BinaryOperatorClass:
 914         return VisitTrueTest(Cond, cast<BinaryOperator>(Ex), tookTrue, BRC,
 915                              R, N);
 916       case Stmt::DeclRefExprClass:
 917         return VisitTrueTest(Cond, cast<DeclRefExpr>(Ex), tookTrue, BRC,
 918                              R, N);
 919       case Stmt::UnaryOperatorClass: {
 920         const UnaryOperator *UO = cast<UnaryOperator>(Ex);
 921         if (UO->getOpcode() == UO_LNot) {
 922           tookTrue = !tookTrue;
 923           Ex = UO->getSubExpr();
 924           continue;
 925         }
 926         return 0;
 927       }
 928     }
 929   }
 930 }
 931
 932 bool ConditionBRVisitor::patternMatch(const Expr *Ex, llvm::raw_ostream &Out,
 933                                       BugReporterContext &BRC,
 934                                       BugReport &report,
 935                                       const ExplodedNode *N,
 936                                       llvm::Optional<bool> &prunable) {
 937   const Expr *OriginalExpr = Ex;
 938   Ex = Ex->IgnoreParenCasts();
 939
 940   if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(Ex)) {
 941     const bool quotes = isa<VarDecl>(DR->getDecl());
 942     if (quotes) {
 943       Out << '\'';
 944       const LocationContext *LCtx = N->getLocationContext();
 945       const ProgramState *state = N->getState().getPtr();
 946       if (const MemRegion *R = state->getLValue(cast<VarDecl>(DR->getDecl()),
 947                                                 LCtx).getAsRegion()) {
 948         if (report.isInteresting(R))
 949           prunable = false;
 950         else {
 951           const ProgramState *state = N->getState().getPtr();
 952           SVal V = state->getSVal(R);
 953           if (report.isInteresting(V))
 954             prunable = false;
 955         }
 956       }
 957     }
 958     Out << DR->getDecl()->getDeclName().getAsString();
 959     if (quotes)
 960       Out << '\'';
 961     return quotes;
 962   }
 963
 964   if (const IntegerLiteral *IL = dyn_cast<IntegerLiteral>(Ex)) {
 965     QualType OriginalTy = OriginalExpr->getType();
 966     if (OriginalTy->isPointerType()) {
 967       if (IL->getValue() == 0) {
 968         Out << "null";
 969         return false;
 970       }
 971     }
 972     else if (OriginalTy->isObjCObjectPointerType()) {
 973       if (IL->getValue() == 0) {
 974         Out << "nil";
 975         return false;
 976       }
 977     }
 978
 979     Out << IL->getValue();
 980     return false;
 981   }
 982
 983   return false;
 984 }
 985
 986 PathDiagnosticPiece *
 987 ConditionBRVisitor::VisitTrueTest(const Expr *Cond,
 988                                   const BinaryOperator *BExpr,
 989                                   const bool tookTrue,
 990                                   BugReporterContext &BRC,
 991                                   BugReport &R,
 992                                   const ExplodedNode *N) {
 993
 994   bool shouldInvert = false;
 995   llvm::Optional<bool> shouldPrune;
 996
 997   SmallString<128> LhsString, RhsString;
 998   {
 999     llvm::raw_svector_ostream OutLHS(LhsString), OutRHS(RhsString);
1000     const bool isVarLHS = patternMatch(BExpr->getLHS(), OutLHS, BRC, R, N,
1001                                        shouldPrune);
1002     const bool isVarRHS = patternMatch(BExpr->getRHS(), OutRHS, BRC, R, N,
1003                                        shouldPrune);
1004
1005     shouldInvert = !isVarLHS && isVarRHS;
1006   }
1007
1008   BinaryOperator::Opcode Op = BExpr->getOpcode();
1009
1010   if (BinaryOperator::isAssignmentOp(Op)) {
1011     // For assignment operators, all that we care about is that the LHS
1012     // evaluates to "true" or "false".
1013     return VisitConditionVariable(LhsString, BExpr->getLHS(), tookTrue,
1014                                   BRC, R, N);
1015   }
1016
1017   // For non-assignment operations, we require that we can understand
1018   // both the LHS and RHS.
1019   if (LhsString.empty() || RhsString.empty())
1020     return 0;
1021
1022   // Should we invert the strings if the LHS is not a variable name?
1023   SmallString<256> buf;
1024   llvm::raw_svector_ostream Out(buf);
1025   Out << "Assuming " << (shouldInvert ? RhsString : LhsString) << " is ";
1026
1027   // Do we need to invert the opcode?
1028   if (shouldInvert)
1029     switch (Op) {
1030       default: break;
1031       case BO_LT: Op = BO_GT; break;
1032       case BO_GT: Op = BO_LT; break;
1033       case BO_LE: Op = BO_GE; break;
1034       case BO_GE: Op = BO_LE; break;
1035     }
1036
1037   if (!tookTrue)
1038     switch (Op) {
1039       case BO_EQ: Op = BO_NE; break;
1040       case BO_NE: Op = BO_EQ; break;
1041       case BO_LT: Op = BO_GE; break;
1042       case BO_GT: Op = BO_LE; break;
1043       case BO_LE: Op = BO_GT; break;
1044       case BO_GE: Op = BO_LT; break;
1045       default:
1046         return 0;
1047     }
1048
1049   switch (Op) {
1050     case BO_EQ:
1051       Out << "equal to ";
1052       break;
1053     case BO_NE:
1054       Out << "not equal to ";
1055       break;
1056     default:
1057       Out << BinaryOperator::getOpcodeStr(Op) << ' ';
1058       break;
1059   }
1060
1061   Out << (shouldInvert ? LhsString : RhsString);
1062   const LocationContext *LCtx = N->getLocationContext();
1063   PathDiagnosticLocation Loc(Cond, BRC.getSourceManager(), LCtx);
1064   PathDiagnosticEventPiece *event =
1065     new PathDiagnosticEventPiece(Loc, Out.str());
1066   if (shouldPrune.hasValue())
1067     event->setPrunable(shouldPrune.getValue());
1068   return event;
1069 }
1070
1071 PathDiagnosticPiece *
1072 ConditionBRVisitor::VisitConditionVariable(StringRef LhsString,
1073                                            const Expr *CondVarExpr,
1074                                            const bool tookTrue,
1075                                            BugReporterContext &BRC,
1076                                            BugReport &report,
1077                                            const ExplodedNode *N) {
1078   // FIXME: If there's already a constraint tracker for this variable,
1079   // we shouldn't emit anything here (c.f. the double note in
1080   // test/Analysis/inlining/path-notes.c)
1081   SmallString<256> buf;
1082   llvm::raw_svector_ostream Out(buf);
1083   Out << "Assuming " << LhsString << " is ";
1084
1085   QualType Ty = CondVarExpr->getType();
1086
1087   if (Ty->isPointerType())
1088     Out << (tookTrue ? "not null" : "null");
1089   else if (Ty->isObjCObjectPointerType())
1090     Out << (tookTrue ? "not nil" : "nil");
1091   else if (Ty->isBooleanType())
1092     Out << (tookTrue ? "true" : "false");
1093   else if (Ty->isIntegerType())
1094     Out << (tookTrue ? "non-zero" : "zero");
1095   else
1096     return 0;
1097
1098   const LocationContext *LCtx = N->getLocationContext();
1099   PathDiagnosticLocation Loc(CondVarExpr, BRC.getSourceManager(), LCtx);
1100   PathDiagnosticEventPiece *event =
1101     new PathDiagnosticEventPiece(Loc, Out.str());
1102
1103   if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(CondVarExpr)) {
1104     if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) {
1105       const ProgramState *state = N->getState().getPtr();
1106       if (const MemRegion *R = state->getLValue(VD, LCtx).getAsRegion()) {
1107         if (report.isInteresting(R))
1108           event->setPrunable(false);
1109       }
1110     }
1111   }
1112
1113   return event;
1114 }
1115
1116 PathDiagnosticPiece *
1117 ConditionBRVisitor::VisitTrueTest(const Expr *Cond,
1118                                   const DeclRefExpr *DR,
1119                                   const bool tookTrue,
1120                                   BugReporterContext &BRC,
1121                                   BugReport &report,
1122                                   const ExplodedNode *N) {
1123
1124   const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl());
1125   if (!VD)
1126     return 0;
1127
1128   SmallString<256> Buf;
1129   llvm::raw_svector_ostream Out(Buf);
1130
1131   Out << "Assuming '";
1132   VD->getDeclName().printName(Out);
1133   Out << "' is ";
1134
1135   QualType VDTy = VD->getType();
1136
1137   if (VDTy->isPointerType())
1138     Out << (tookTrue ? "non-null" : "null");
1139   else if (VDTy->isObjCObjectPointerType())
1140     Out << (tookTrue ? "non-nil" : "nil");
1141   else if (VDTy->isScalarType())
1142     Out << (tookTrue ? "not equal to 0" : "0");
1143   else
1144     return 0;
1145
1146   const LocationContext *LCtx = N->getLocationContext();
1147   PathDiagnosticLocation Loc(Cond, BRC.getSourceManager(), LCtx);
1148   PathDiagnosticEventPiece *event =
1149     new PathDiagnosticEventPiece(Loc, Out.str());
1150
1151   const ProgramState *state = N->getState().getPtr();
1152   if (const MemRegion *R = state->getLValue(VD, LCtx).getAsRegion()) {
1153     if (report.isInteresting(R))
1154       event->setPrunable(false);
1155     else {
1156       SVal V = state->getSVal(R);
1157       if (report.isInteresting(V))
1158         event->setPrunable(false);
1159     }
1160   }
1161   return event;
1162 }
1163
1164 PathDiagnosticPiece *
1165 UndefOrNullArgVisitor::VisitNode(const ExplodedNode *N,
1166                                   const ExplodedNode *PrevN,
1167                                   BugReporterContext &BRC,
1168                                   BugReport &BR) {
1169
1170   ProgramStateRef State = N->getState();
1171   ProgramPoint ProgLoc = N->getLocation();
1172
1173   // We are only interested in visiting CallEnter nodes.
1174   CallEnter *CEnter = dyn_cast<CallEnter>(&ProgLoc);
1175   if (!CEnter)
1176     return 0;
1177
1178   // Check if one of the arguments is the region the visitor is tracking.
1179   CallEventManager &CEMgr = BRC.getStateManager().getCallEventManager();
1180   CallEventRef<> Call = CEMgr.getCaller(CEnter->getCalleeContext(), State);
1181   unsigned Idx = 0;
1182   for (CallEvent::param_iterator I = Call->param_begin(),
1183                                  E = Call->param_end(); I != E; ++I, ++Idx) {
1184     const MemRegion *ArgReg = Call->getArgSVal(Idx).getAsRegion();
1185
1186     // Are we tracking the argument or its subregion?
1187     if ( !ArgReg || (ArgReg != R && !R->isSubRegionOf(ArgReg->StripCasts())))
1188       continue;
1189
1190     // Check the function parameter type.
1191     const ParmVarDecl *ParamDecl = *I;
1192     assert(ParamDecl && "Formal parameter has no decl?");
1193     QualType T = ParamDecl->getType();
1194
1195     if (!(T->isAnyPointerType() || T->isReferenceType())) {
1196       // Function can only change the value passed in by address.
1197       continue;
1198     }
1199
1200     // If it is a const pointer value, the function does not intend to
1201     // change the value.
1202     if (T->getPointeeType().isConstQualified())
1203       continue;
1204
1205     // Mark the call site (LocationContext) as interesting if the value of the
1206     // argument is undefined or '0'/'NULL'.
1207     SVal BoundVal = State->getSVal(R);
1208     if (BoundVal.isUndef() || BoundVal.isZeroConstant()) {
1209       BR.markInteresting(CEnter->getCalleeContext());
1210       return 0;
1211     }
1212   }
1213   return 0;
1214 }