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