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