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