BugReporterVisitors.cpp revision b9d4e5e3bb235f1149e99d3c833ff7cb3474c9f1 
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
470PathDiagnosticPiece *
471TrackConstraintBRVisitor::VisitNode(const ExplodedNode *N,
472                                    const ExplodedNode *PrevN,
473                                    BugReporterContext &BRC,
474                                    BugReport &BR) {
475  if (isSatisfied)
476    return NULL;
477
478  // Check if in the previous state it was feasible for this constraint
479  // to *not* be true.
480  if (PrevN->getState()->assume(Constraint, !Assumption)) {
481
482    isSatisfied = true;
483
484    // As a sanity check, make sure that the negation of the constraint
485    // was infeasible in the current state.  If it is feasible, we somehow
486    // missed the transition point.
487    if (N->getState()->assume(Constraint, !Assumption))
488      return NULL;
489
490    // We found the transition point for the constraint.  We now need to
491    // pretty-print the constraint. (work-in-progress)
492    std::string sbuf;
493    llvm::raw_string_ostream os(sbuf);
494
495    if (isa<Loc>(Constraint)) {
496      os << "Assuming pointer value is ";
497      os << (Assumption ? "non-null" : "null");
498    }
499
500    if (os.str().empty())
501      return NULL;
502
503    // Construct a new PathDiagnosticPiece.
504    ProgramPoint P = N->getLocation();
505    PathDiagnosticLocation L =
506      PathDiagnosticLocation::create(P, BRC.getSourceManager());
507    if (!L.isValid())
508      return NULL;
509    return new PathDiagnosticEventPiece(L, os.str());
510  }
511
512  return NULL;
513}
514
515void bugreporter::trackNullOrUndefValue(const ExplodedNode *N, const Stmt *S,
516                                        BugReport &report) {
517  if (!S || !N)
518    return;
519
520  if (const OpaqueValueExpr *OVE = dyn_cast<OpaqueValueExpr>(S))
521    S = OVE->getSourceExpr();
522
523  ProgramStateManager &StateMgr = N->getState()->getStateManager();
524
525  // Walk through nodes until we get one that matches the statement exactly.
526  while (N) {
527    const ProgramPoint &pp = N->getLocation();
528    if (const PostStmt *ps = dyn_cast<PostStmt>(&pp)) {
529      if (ps->getStmt() == S)
530        break;
531    } else if (const CallExitEnd *CEE = dyn_cast<CallExitEnd>(&pp)) {
532      if (CEE->getCalleeContext()->getCallSite() == S)
533        break;
534    }
535    N = N->getFirstPred();
536  }
537
538  if (!N)
539    return;
540
541  ProgramStateRef state = N->getState();
542
543  // See if the expression we're interested refers to a variable.
544  // If so, we can track both its contents and constraints on its value.
545  if (const Expr *Ex = dyn_cast<Expr>(S)) {
546    // Strip off parens and casts. Note that this will never have issues with
547    // C++ user-defined implicit conversions, because those have a constructor
548    // or function call inside.
549    Ex = Ex->IgnoreParenCasts();
550    if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(Ex)) {
551      // FIXME: Right now we only track VarDecls because it's non-trivial to
552      // get a MemRegion for any other DeclRefExprs. <rdar://problem/12114812>
553      if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) {
554        const VarRegion *R =
555          StateMgr.getRegionManager().getVarRegion(VD, N->getLocationContext());
556
557        // Mark both the variable region and its contents as interesting.
558        SVal V = state->getRawSVal(loc::MemRegionVal(R));
559        report.markInteresting(R);
560        report.markInteresting(V);
561        report.addVisitor(new UndefOrNullArgVisitor(R));
562
563        // If the contents are symbolic, find out when they became null.
564        if (V.getAsLocSymbol()) {
565          BugReporterVisitor *ConstraintTracker
566            = new TrackConstraintBRVisitor(cast<DefinedSVal>(V), false);
567          report.addVisitor(ConstraintTracker);
568        }
569
570        report.addVisitor(new FindLastStoreBRVisitor(V, R));
571        return;
572      }
573    }
574  }
575
576  // If the expression does NOT refer to a variable, we can still track
577  // constraints on its contents.
578  SVal V = state->getSValAsScalarOrLoc(S, N->getLocationContext());
579
580  // Uncomment this to find cases where we aren't properly getting the
581  // base value that was dereferenced.
582  // assert(!V.isUnknownOrUndef());
583
584  // Is it a symbolic value?
585  if (loc::MemRegionVal *L = dyn_cast<loc::MemRegionVal>(&V)) {
586    // At this point we are dealing with the region's LValue.
587    // However, if the rvalue is a symbolic region, we should track it as well.
588    SVal RVal = state->getSVal(L->getRegion());
589    const MemRegion *RegionRVal = RVal.getAsRegion();
590    report.addVisitor(new UndefOrNullArgVisitor(L->getRegion()));
591
592
593    if (RegionRVal && isa<SymbolicRegion>(RegionRVal)) {
594      report.markInteresting(RegionRVal);
595      report.addVisitor(new TrackConstraintBRVisitor(
596        loc::MemRegionVal(RegionRVal), false));
597    }
598  } else {
599    // Otherwise, if the value came from an inlined function call,
600    // we should at least make sure that function isn't pruned in our output.
601    if (const Expr *E = dyn_cast<Expr>(S))
602      S = E->IgnoreParenCasts();
603    ReturnVisitor::addVisitorIfNecessary(N, S, report);
604  }
605}
606
607BugReporterVisitor *
608FindLastStoreBRVisitor::createVisitorObject(const ExplodedNode *N,
609                                            const MemRegion *R) {
610  assert(R && "The memory region is null.");
611
612  ProgramStateRef state = N->getState();
613  SVal V = state->getSVal(R);
614  if (V.isUnknown())
615    return 0;
616
617  return new FindLastStoreBRVisitor(V, R);
618}
619
620
621PathDiagnosticPiece *NilReceiverBRVisitor::VisitNode(const ExplodedNode *N,
622                                                     const ExplodedNode *PrevN,
623                                                     BugReporterContext &BRC,
624                                                     BugReport &BR) {
625  const PostStmt *P = N->getLocationAs<PostStmt>();
626  if (!P)
627    return 0;
628  const ObjCMessageExpr *ME = P->getStmtAs<ObjCMessageExpr>();
629  if (!ME)
630    return 0;
631  const Expr *Receiver = ME->getInstanceReceiver();
632  if (!Receiver)
633    return 0;
634  ProgramStateRef state = N->getState();
635  const SVal &V = state->getSVal(Receiver, N->getLocationContext());
636  const DefinedOrUnknownSVal *DV = dyn_cast<DefinedOrUnknownSVal>(&V);
637  if (!DV)
638    return 0;
639  state = state->assume(*DV, true);
640  if (state)
641    return 0;
642
643  // The receiver was nil, and hence the method was skipped.
644  // Register a BugReporterVisitor to issue a message telling us how
645  // the receiver was null.
646  bugreporter::trackNullOrUndefValue(N, Receiver, BR);
647  // Issue a message saying that the method was skipped.
648  PathDiagnosticLocation L(Receiver, BRC.getSourceManager(),
649                                     N->getLocationContext());
650  return new PathDiagnosticEventPiece(L, "No method is called "
651      "because the receiver is nil");
652}
653
654// Registers every VarDecl inside a Stmt with a last store visitor.
655void FindLastStoreBRVisitor::registerStatementVarDecls(BugReport &BR,
656                                                       const Stmt *S) {
657  const ExplodedNode *N = BR.getErrorNode();
658  std::deque<const Stmt *> WorkList;
659  WorkList.push_back(S);
660
661  while (!WorkList.empty()) {
662    const Stmt *Head = WorkList.front();
663    WorkList.pop_front();
664
665    ProgramStateRef state = N->getState();
666    ProgramStateManager &StateMgr = state->getStateManager();
667
668    if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(Head)) {
669      if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) {
670        const VarRegion *R =
671        StateMgr.getRegionManager().getVarRegion(VD, N->getLocationContext());
672
673        // What did we load?
674        SVal V = state->getSVal(S, N->getLocationContext());
675
676        if (isa<loc::ConcreteInt>(V) || isa<nonloc::ConcreteInt>(V)) {
677          // Register a new visitor with the BugReport.
678          BR.addVisitor(new FindLastStoreBRVisitor(V, R));
679        }
680      }
681    }
682
683    for (Stmt::const_child_iterator I = Head->child_begin();
684        I != Head->child_end(); ++I)
685      WorkList.push_back(*I);
686  }
687}
688
689//===----------------------------------------------------------------------===//
690// Visitor that tries to report interesting diagnostics from conditions.
691//===----------------------------------------------------------------------===//
692PathDiagnosticPiece *ConditionBRVisitor::VisitNode(const ExplodedNode *N,
693                                                   const ExplodedNode *Prev,
694                                                   BugReporterContext &BRC,
695                                                   BugReport &BR) {
696  PathDiagnosticPiece *piece = VisitNodeImpl(N, Prev, BRC, BR);
697  if (PathDiagnosticEventPiece *ev =
698      dyn_cast_or_null<PathDiagnosticEventPiece>(piece))
699    ev->setPrunable(true, /* override */ false);
700  return piece;
701}
702
703PathDiagnosticPiece *ConditionBRVisitor::VisitNodeImpl(const ExplodedNode *N,
704                                                       const ExplodedNode *Prev,
705                                                       BugReporterContext &BRC,
706                                                       BugReport &BR) {
707
708  ProgramPoint progPoint = N->getLocation();
709  ProgramStateRef CurrentState = N->getState();
710  ProgramStateRef PrevState = Prev->getState();
711
712  // Compare the GDMs of the state, because that is where constraints
713  // are managed.  Note that ensure that we only look at nodes that
714  // were generated by the analyzer engine proper, not checkers.
715  if (CurrentState->getGDM().getRoot() ==
716      PrevState->getGDM().getRoot())
717    return 0;
718
719  // If an assumption was made on a branch, it should be caught
720  // here by looking at the state transition.
721  if (const BlockEdge *BE = dyn_cast<BlockEdge>(&progPoint)) {
722    const CFGBlock *srcBlk = BE->getSrc();
723    if (const Stmt *term = srcBlk->getTerminator())
724      return VisitTerminator(term, N, srcBlk, BE->getDst(), BR, BRC);
725    return 0;
726  }
727
728  if (const PostStmt *PS = dyn_cast<PostStmt>(&progPoint)) {
729    // FIXME: Assuming that BugReporter is a GRBugReporter is a layering
730    // violation.
731    const std::pair<const ProgramPointTag *, const ProgramPointTag *> &tags =
732      cast<GRBugReporter>(BRC.getBugReporter()).
733        getEngine().geteagerlyAssumeBinOpBifurcationTags();
734
735    const ProgramPointTag *tag = PS->getTag();
736    if (tag == tags.first)
737      return VisitTrueTest(cast<Expr>(PS->getStmt()), true,
738                           BRC, BR, N);
739    if (tag == tags.second)
740      return VisitTrueTest(cast<Expr>(PS->getStmt()), false,
741                           BRC, BR, N);
742
743    return 0;
744  }
745
746  return 0;
747}
748
749PathDiagnosticPiece *
750ConditionBRVisitor::VisitTerminator(const Stmt *Term,
751                                    const ExplodedNode *N,
752                                    const CFGBlock *srcBlk,
753                                    const CFGBlock *dstBlk,
754                                    BugReport &R,
755                                    BugReporterContext &BRC) {
756  const Expr *Cond = 0;
757
758  switch (Term->getStmtClass()) {
759  default:
760    return 0;
761  case Stmt::IfStmtClass:
762    Cond = cast<IfStmt>(Term)->getCond();
763    break;
764  case Stmt::ConditionalOperatorClass:
765    Cond = cast<ConditionalOperator>(Term)->getCond();
766    break;
767  }
768
769  assert(Cond);
770  assert(srcBlk->succ_size() == 2);
771  const bool tookTrue = *(srcBlk->succ_begin()) == dstBlk;
772  return VisitTrueTest(Cond, tookTrue, BRC, R, N);
773}
774
775PathDiagnosticPiece *
776ConditionBRVisitor::VisitTrueTest(const Expr *Cond,
777                                  bool tookTrue,
778                                  BugReporterContext &BRC,
779                                  BugReport &R,
780                                  const ExplodedNode *N) {
781
782  const Expr *Ex = Cond;
783
784  while (true) {
785    Ex = Ex->IgnoreParenCasts();
786    switch (Ex->getStmtClass()) {
787      default:
788        return 0;
789      case Stmt::BinaryOperatorClass:
790        return VisitTrueTest(Cond, cast<BinaryOperator>(Ex), tookTrue, BRC,
791                             R, N);
792      case Stmt::DeclRefExprClass:
793        return VisitTrueTest(Cond, cast<DeclRefExpr>(Ex), tookTrue, BRC,
794                             R, N);
795      case Stmt::UnaryOperatorClass: {
796        const UnaryOperator *UO = cast<UnaryOperator>(Ex);
797        if (UO->getOpcode() == UO_LNot) {
798          tookTrue = !tookTrue;
799          Ex = UO->getSubExpr();
800          continue;
801        }
802        return 0;
803      }
804    }
805  }
806}
807
808bool ConditionBRVisitor::patternMatch(const Expr *Ex, llvm::raw_ostream &Out,
809                                      BugReporterContext &BRC,
810                                      BugReport &report,
811                                      const ExplodedNode *N,
812                                      llvm::Optional<bool> &prunable) {
813  const Expr *OriginalExpr = Ex;
814  Ex = Ex->IgnoreParenCasts();
815
816  if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(Ex)) {
817    const bool quotes = isa<VarDecl>(DR->getDecl());
818    if (quotes) {
819      Out << '\'';
820      const LocationContext *LCtx = N->getLocationContext();
821      const ProgramState *state = N->getState().getPtr();
822      if (const MemRegion *R = state->getLValue(cast<VarDecl>(DR->getDecl()),
823                                                LCtx).getAsRegion()) {
824        if (report.isInteresting(R))
825          prunable = false;
826        else {
827          const ProgramState *state = N->getState().getPtr();
828          SVal V = state->getSVal(R);
829          if (report.isInteresting(V))
830            prunable = false;
831        }
832      }
833    }
834    Out << DR->getDecl()->getDeclName().getAsString();
835    if (quotes)
836      Out << '\'';
837    return quotes;
838  }
839
840  if (const IntegerLiteral *IL = dyn_cast<IntegerLiteral>(Ex)) {
841    QualType OriginalTy = OriginalExpr->getType();
842    if (OriginalTy->isPointerType()) {
843      if (IL->getValue() == 0) {
844        Out << "null";
845        return false;
846      }
847    }
848    else if (OriginalTy->isObjCObjectPointerType()) {
849      if (IL->getValue() == 0) {
850        Out << "nil";
851        return false;
852      }
853    }
854
855    Out << IL->getValue();
856    return false;
857  }
858
859  return false;
860}
861
862PathDiagnosticPiece *
863ConditionBRVisitor::VisitTrueTest(const Expr *Cond,
864                                  const BinaryOperator *BExpr,
865                                  const bool tookTrue,
866                                  BugReporterContext &BRC,
867                                  BugReport &R,
868                                  const ExplodedNode *N) {
869
870  bool shouldInvert = false;
871  llvm::Optional<bool> shouldPrune;
872
873  SmallString<128> LhsString, RhsString;
874  {
875    llvm::raw_svector_ostream OutLHS(LhsString), OutRHS(RhsString);
876    const bool isVarLHS = patternMatch(BExpr->getLHS(), OutLHS, BRC, R, N,
877                                       shouldPrune);
878    const bool isVarRHS = patternMatch(BExpr->getRHS(), OutRHS, BRC, R, N,
879                                       shouldPrune);
880
881    shouldInvert = !isVarLHS && isVarRHS;
882  }
883
884  BinaryOperator::Opcode Op = BExpr->getOpcode();
885
886  if (BinaryOperator::isAssignmentOp(Op)) {
887    // For assignment operators, all that we care about is that the LHS
888    // evaluates to "true" or "false".
889    return VisitConditionVariable(LhsString, BExpr->getLHS(), tookTrue,
890                                  BRC, R, N);
891  }
892
893  // For non-assignment operations, we require that we can understand
894  // both the LHS and RHS.
895  if (LhsString.empty() || RhsString.empty())
896    return 0;
897
898  // Should we invert the strings if the LHS is not a variable name?
899  SmallString<256> buf;
900  llvm::raw_svector_ostream Out(buf);
901  Out << "Assuming " << (shouldInvert ? RhsString : LhsString) << " is ";
902
903  // Do we need to invert the opcode?
904  if (shouldInvert)
905    switch (Op) {
906      default: break;
907      case BO_LT: Op = BO_GT; break;
908      case BO_GT: Op = BO_LT; break;
909      case BO_LE: Op = BO_GE; break;
910      case BO_GE: Op = BO_LE; break;
911    }
912
913  if (!tookTrue)
914    switch (Op) {
915      case BO_EQ: Op = BO_NE; break;
916      case BO_NE: Op = BO_EQ; break;
917      case BO_LT: Op = BO_GE; break;
918      case BO_GT: Op = BO_LE; break;
919      case BO_LE: Op = BO_GT; break;
920      case BO_GE: Op = BO_LT; break;
921      default:
922        return 0;
923    }
924
925  switch (Op) {
926    case BO_EQ:
927      Out << "equal to ";
928      break;
929    case BO_NE:
930      Out << "not equal to ";
931      break;
932    default:
933      Out << BinaryOperator::getOpcodeStr(Op) << ' ';
934      break;
935  }
936
937  Out << (shouldInvert ? LhsString : RhsString);
938  const LocationContext *LCtx = N->getLocationContext();
939  PathDiagnosticLocation Loc(Cond, BRC.getSourceManager(), LCtx);
940  PathDiagnosticEventPiece *event =
941    new PathDiagnosticEventPiece(Loc, Out.str());
942  if (shouldPrune.hasValue())
943    event->setPrunable(shouldPrune.getValue());
944  return event;
945}
946
947PathDiagnosticPiece *
948ConditionBRVisitor::VisitConditionVariable(StringRef LhsString,
949                                           const Expr *CondVarExpr,
950                                           const bool tookTrue,
951                                           BugReporterContext &BRC,
952                                           BugReport &report,
953                                           const ExplodedNode *N) {
954  // FIXME: If there's already a constraint tracker for this variable,
955  // we shouldn't emit anything here (c.f. the double note in
956  // test/Analysis/inlining/path-notes.c)
957  SmallString<256> buf;
958  llvm::raw_svector_ostream Out(buf);
959  Out << "Assuming " << LhsString << " is ";
960
961  QualType Ty = CondVarExpr->getType();
962
963  if (Ty->isPointerType())
964    Out << (tookTrue ? "not null" : "null");
965  else if (Ty->isObjCObjectPointerType())
966    Out << (tookTrue ? "not nil" : "nil");
967  else if (Ty->isBooleanType())
968    Out << (tookTrue ? "true" : "false");
969  else if (Ty->isIntegerType())
970    Out << (tookTrue ? "non-zero" : "zero");
971  else
972    return 0;
973
974  const LocationContext *LCtx = N->getLocationContext();
975  PathDiagnosticLocation Loc(CondVarExpr, BRC.getSourceManager(), LCtx);
976  PathDiagnosticEventPiece *event =
977    new PathDiagnosticEventPiece(Loc, Out.str());
978
979  if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(CondVarExpr)) {
980    if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) {
981      const ProgramState *state = N->getState().getPtr();
982      if (const MemRegion *R = state->getLValue(VD, LCtx).getAsRegion()) {
983        if (report.isInteresting(R))
984          event->setPrunable(false);
985      }
986    }
987  }
988
989  return event;
990}
991
992PathDiagnosticPiece *
993ConditionBRVisitor::VisitTrueTest(const Expr *Cond,
994                                  const DeclRefExpr *DR,
995                                  const bool tookTrue,
996                                  BugReporterContext &BRC,
997                                  BugReport &report,
998                                  const ExplodedNode *N) {
999
1000  const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl());
1001  if (!VD)
1002    return 0;
1003
1004  SmallString<256> Buf;
1005  llvm::raw_svector_ostream Out(Buf);
1006
1007  Out << "Assuming '";
1008  VD->getDeclName().printName(Out);
1009  Out << "' is ";
1010
1011  QualType VDTy = VD->getType();
1012
1013  if (VDTy->isPointerType())
1014    Out << (tookTrue ? "non-null" : "null");
1015  else if (VDTy->isObjCObjectPointerType())
1016    Out << (tookTrue ? "non-nil" : "nil");
1017  else if (VDTy->isScalarType())
1018    Out << (tookTrue ? "not equal to 0" : "0");
1019  else
1020    return 0;
1021
1022  const LocationContext *LCtx = N->getLocationContext();
1023  PathDiagnosticLocation Loc(Cond, BRC.getSourceManager(), LCtx);
1024  PathDiagnosticEventPiece *event =
1025    new PathDiagnosticEventPiece(Loc, Out.str());
1026
1027  const ProgramState *state = N->getState().getPtr();
1028  if (const MemRegion *R = state->getLValue(VD, LCtx).getAsRegion()) {
1029    if (report.isInteresting(R))
1030      event->setPrunable(false);
1031    else {
1032      SVal V = state->getSVal(R);
1033      if (report.isInteresting(V))
1034        event->setPrunable(false);
1035    }
1036  }
1037  return event;
1038}
1039
1040PathDiagnosticPiece *
1041UndefOrNullArgVisitor::VisitNode(const ExplodedNode *N,
1042                                  const ExplodedNode *PrevN,
1043                                  BugReporterContext &BRC,
1044                                  BugReport &BR) {
1045
1046  ProgramStateRef State = N->getState();
1047  ProgramPoint ProgLoc = N->getLocation();
1048
1049  // We are only interested in visiting CallEnter nodes.
1050  CallEnter *CEnter = dyn_cast<CallEnter>(&ProgLoc);
1051  if (!CEnter)
1052    return 0;
1053
1054  // Check if one of the arguments is the region the visitor is tracking.
1055  CallEventManager &CEMgr = BRC.getStateManager().getCallEventManager();
1056  CallEventRef<> Call = CEMgr.getCaller(CEnter->getCalleeContext(), State);
1057  unsigned Idx = 0;
1058  for (CallEvent::param_iterator I = Call->param_begin(),
1059                                 E = Call->param_end(); I != E; ++I, ++Idx) {
1060    const MemRegion *ArgReg = Call->getArgSVal(Idx).getAsRegion();
1061
1062    // Are we tracking the argument or its subregion?
1063    if ( !ArgReg || (ArgReg != R && !R->isSubRegionOf(ArgReg->StripCasts())))
1064      continue;
1065
1066    // Check the function parameter type.
1067    const ParmVarDecl *ParamDecl = *I;
1068    assert(ParamDecl && "Formal parameter has no decl?");
1069    QualType T = ParamDecl->getType();
1070
1071    if (!(T->isAnyPointerType() || T->isReferenceType())) {
1072      // Function can only change the value passed in by address.
1073      continue;
1074    }
1075
1076    // If it is a const pointer value, the function does not intend to
1077    // change the value.
1078    if (T->getPointeeType().isConstQualified())
1079      continue;
1080
1081    // Mark the call site (LocationContext) as interesting if the value of the
1082    // argument is undefined or '0'/'NULL'.
1083    SVal BoundVal = State->getSVal(R);
1084    if (BoundVal.isUndef() || BoundVal.isZeroConstant()) {
1085      BR.markInteresting(CEnter->getCalleeContext());
1086      return 0;
1087    }
1088  }
1089  return 0;
1090}
1091