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