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