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