BugReporterVisitors.cpp revision 6a329ee7567cf3267ffab2bc755ea8c773d967e7 
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
28using namespace clang;
29using namespace ento;
30
31//===----------------------------------------------------------------------===//
32// Utility functions.
33//===----------------------------------------------------------------------===//
34
35bool 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
42const 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
81const 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
88const 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
99PathDiagnosticPiece*
100BugReporterVisitor::getEndPath(BugReporterContext &BRC,
101                               const ExplodedNode *EndPathNode,
102                               BugReport &BR) {
103  return 0;
104}
105
106PathDiagnosticPiece*
107BugReporterVisitor::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
128namespace {
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.
136class ReturnVisitor : public BugReporterVisitorImpl<ReturnVisitor> {
137  const StackFrameContext *StackFrame;
138  enum {
139    Initial,
140    MaybeSuppress,
141    Satisfied
142  } Mode;
143
144public:
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
350void 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
357PathDiagnosticPiece *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
548void 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.
557const char *TrackConstraintBRVisitor::getTag() {
558  return "TrackConstraintBRVisitor";
559}
560
561PathDiagnosticPiece *
562TrackConstraintBRVisitor::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
609bool 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
722BugReporterVisitor *
723FindLastStoreBRVisitor::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
736PathDiagnosticPiece *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.
770void 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.
810const char *ConditionBRVisitor::getTag() {
811  return "ConditionBRVisitor";
812}
813
814PathDiagnosticPiece *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
827PathDiagnosticPiece *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
873PathDiagnosticPiece *
874ConditionBRVisitor::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
899PathDiagnosticPiece *
900ConditionBRVisitor::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
932bool 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
986PathDiagnosticPiece *
987ConditionBRVisitor::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
1071PathDiagnosticPiece *
1072ConditionBRVisitor::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
1116PathDiagnosticPiece *
1117ConditionBRVisitor::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
1164PathDiagnosticPiece *
1165UndefOrNullArgVisitor::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}
1215