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