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