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