BugReporterVisitors.cpp revision 882998923889a2fcce9b49696506c499e22cf38f 
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
15#include "clang/AST/Expr.h"
16#include "clang/AST/ExprObjC.h"
17#include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h"
18#include "clang/StaticAnalyzer/Core/BugReporter/PathDiagnostic.h"
19#include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h"
20#include "clang/StaticAnalyzer/Core/PathSensitive/GRState.h"
21
22using namespace clang;
23using namespace ento;
24
25//===----------------------------------------------------------------------===//
26// Utility functions.
27//===----------------------------------------------------------------------===//
28
29const Stmt *bugreporter::GetDerefExpr(const ExplodedNode *N) {
30  // Pattern match for a few useful cases (do something smarter later):
31  //   a[0], p->f, *p
32  const Stmt *S = N->getLocationAs<PostStmt>()->getStmt();
33
34  if (const UnaryOperator *U = dyn_cast<UnaryOperator>(S)) {
35    if (U->getOpcode() == UO_Deref)
36      return U->getSubExpr()->IgnoreParenCasts();
37  }
38  else if (const MemberExpr *ME = dyn_cast<MemberExpr>(S)) {
39    return ME->getBase()->IgnoreParenCasts();
40  }
41  else if (const ArraySubscriptExpr *AE = dyn_cast<ArraySubscriptExpr>(S)) {
42    return AE->getBase();
43  }
44
45  return NULL;
46}
47
48const Stmt *bugreporter::GetDenomExpr(const ExplodedNode *N) {
49  const Stmt *S = N->getLocationAs<PreStmt>()->getStmt();
50  if (const BinaryOperator *BE = dyn_cast<BinaryOperator>(S))
51    return BE->getRHS();
52  return NULL;
53}
54
55const Stmt *bugreporter::GetCalleeExpr(const ExplodedNode *N) {
56  // Callee is checked as a PreVisit to the CallExpr.
57  const Stmt *S = N->getLocationAs<PreStmt>()->getStmt();
58  if (const CallExpr *CE = dyn_cast<CallExpr>(S))
59    return CE->getCallee();
60  return NULL;
61}
62
63const Stmt *bugreporter::GetRetValExpr(const ExplodedNode *N) {
64  const Stmt *S = N->getLocationAs<PostStmt>()->getStmt();
65  if (const ReturnStmt *RS = dyn_cast<ReturnStmt>(S))
66    return RS->getRetValue();
67  return NULL;
68}
69
70//===----------------------------------------------------------------------===//
71// Definitions for bug reporter visitors.
72//===----------------------------------------------------------------------===//
73
74namespace {
75class FindLastStoreBRVisitor : public BugReporterVisitor {
76  const MemRegion *R;
77  SVal V;
78  bool satisfied;
79  const ExplodedNode *StoreSite;
80public:
81  FindLastStoreBRVisitor(SVal v, const MemRegion *r)
82  : R(r), V(v), satisfied(false), StoreSite(0) {}
83
84  virtual void Profile(llvm::FoldingSetNodeID &ID) const {
85    static int tag = 0;
86    ID.AddPointer(&tag);
87    ID.AddPointer(R);
88    ID.Add(V);
89  }
90
91  PathDiagnosticPiece* VisitNode(const ExplodedNode *N,
92                                 const ExplodedNode *PrevN,
93                                 BugReporterContext& BRC) {
94
95    if (satisfied)
96      return NULL;
97
98    if (!StoreSite) {
99      const ExplodedNode *Node = N, *Last = NULL;
100
101      for ( ; Node ; Last = Node, Node = Node->getFirstPred()) {
102
103        if (const VarRegion *VR = dyn_cast<VarRegion>(R)) {
104          if (const PostStmt *P = Node->getLocationAs<PostStmt>())
105            if (const DeclStmt *DS = P->getStmtAs<DeclStmt>())
106              if (DS->getSingleDecl() == VR->getDecl()) {
107                Last = Node;
108                break;
109              }
110        }
111
112        if (Node->getState()->getSVal(R) != V)
113          break;
114      }
115
116      if (!Node || !Last) {
117        satisfied = true;
118        return NULL;
119      }
120
121      StoreSite = Last;
122    }
123
124    if (StoreSite != N)
125      return NULL;
126
127    satisfied = true;
128    llvm::SmallString<256> sbuf;
129    llvm::raw_svector_ostream os(sbuf);
130
131    if (const PostStmt *PS = N->getLocationAs<PostStmt>()) {
132      if (const DeclStmt *DS = PS->getStmtAs<DeclStmt>()) {
133
134        if (const VarRegion *VR = dyn_cast<VarRegion>(R)) {
135          os << "Variable '" << VR->getDecl() << "' ";
136        }
137        else
138          return NULL;
139
140        if (isa<loc::ConcreteInt>(V)) {
141          bool b = false;
142          if (R->isBoundable()) {
143            if (const TypedRegion *TR = dyn_cast<TypedRegion>(R)) {
144              if (TR->getValueType()->isObjCObjectPointerType()) {
145                os << "initialized to nil";
146                b = true;
147              }
148            }
149          }
150
151          if (!b)
152            os << "initialized to a null pointer value";
153        }
154        else if (isa<nonloc::ConcreteInt>(V)) {
155          os << "initialized to " << cast<nonloc::ConcreteInt>(V).getValue();
156        }
157        else if (V.isUndef()) {
158          if (isa<VarRegion>(R)) {
159            const VarDecl *VD = cast<VarDecl>(DS->getSingleDecl());
160            if (VD->getInit())
161              os << "initialized to a garbage value";
162            else
163              os << "declared without an initial value";
164          }
165        }
166      }
167    }
168
169    if (os.str().empty()) {
170      if (isa<loc::ConcreteInt>(V)) {
171        bool b = false;
172        if (R->isBoundable()) {
173          if (const TypedRegion *TR = dyn_cast<TypedRegion>(R)) {
174            if (TR->getValueType()->isObjCObjectPointerType()) {
175              os << "nil object reference stored to ";
176              b = true;
177            }
178          }
179        }
180
181        if (!b)
182          os << "Null pointer value stored to ";
183      }
184      else if (V.isUndef()) {
185        os << "Uninitialized value stored to ";
186      }
187      else if (isa<nonloc::ConcreteInt>(V)) {
188        os << "The value " << cast<nonloc::ConcreteInt>(V).getValue()
189           << " is assigned to ";
190      }
191      else
192        return NULL;
193
194      if (const VarRegion *VR = dyn_cast<VarRegion>(R)) {
195        os << '\'' << VR->getDecl() << '\'';
196      }
197      else
198        return NULL;
199    }
200
201    // FIXME: Refactor this into BugReporterContext.
202    const Stmt *S = 0;
203    ProgramPoint P = N->getLocation();
204
205    if (BlockEdge *BE = dyn_cast<BlockEdge>(&P)) {
206      const CFGBlock *BSrc = BE->getSrc();
207      S = BSrc->getTerminatorCondition();
208    }
209    else if (PostStmt *PS = dyn_cast<PostStmt>(&P)) {
210      S = PS->getStmt();
211    }
212
213    if (!S)
214      return NULL;
215
216    // Construct a new PathDiagnosticPiece.
217    PathDiagnosticLocation L(S, BRC.getSourceManager());
218    return new PathDiagnosticEventPiece(L, os.str());
219  }
220};
221
222
223static void registerFindLastStore(BugReporterContext& BRC, const MemRegion *R,
224                                  SVal V) {
225  BRC.addVisitor(new FindLastStoreBRVisitor(V, R));
226}
227
228class TrackConstraintBRVisitor : public BugReporterVisitor {
229  DefinedSVal Constraint;
230  const bool Assumption;
231  bool isSatisfied;
232public:
233  TrackConstraintBRVisitor(DefinedSVal constraint, bool assumption)
234  : Constraint(constraint), Assumption(assumption), isSatisfied(false) {}
235
236  void Profile(llvm::FoldingSetNodeID &ID) const {
237    static int tag = 0;
238    ID.AddPointer(&tag);
239    ID.AddBoolean(Assumption);
240    ID.Add(Constraint);
241  }
242
243  PathDiagnosticPiece* VisitNode(const ExplodedNode *N,
244                                 const ExplodedNode *PrevN,
245                                 BugReporterContext& BRC) {
246    if (isSatisfied)
247      return NULL;
248
249    // Check if in the previous state it was feasible for this constraint
250    // to *not* be true.
251    if (PrevN->getState()->assume(Constraint, !Assumption)) {
252
253      isSatisfied = true;
254
255      // As a sanity check, make sure that the negation of the constraint
256      // was infeasible in the current state.  If it is feasible, we somehow
257      // missed the transition point.
258      if (N->getState()->assume(Constraint, !Assumption))
259        return NULL;
260
261      // We found the transition point for the constraint.  We now need to
262      // pretty-print the constraint. (work-in-progress)
263      std::string sbuf;
264      llvm::raw_string_ostream os(sbuf);
265
266      if (isa<Loc>(Constraint)) {
267        os << "Assuming pointer value is ";
268        os << (Assumption ? "non-null" : "null");
269      }
270
271      if (os.str().empty())
272        return NULL;
273
274      // FIXME: Refactor this into BugReporterContext.
275      const Stmt *S = 0;
276      ProgramPoint P = N->getLocation();
277
278      if (BlockEdge *BE = dyn_cast<BlockEdge>(&P)) {
279        const CFGBlock *BSrc = BE->getSrc();
280        S = BSrc->getTerminatorCondition();
281      }
282      else if (PostStmt *PS = dyn_cast<PostStmt>(&P)) {
283        S = PS->getStmt();
284      }
285
286      if (!S)
287        return NULL;
288
289      // Construct a new PathDiagnosticPiece.
290      PathDiagnosticLocation L(S, BRC.getSourceManager());
291      return new PathDiagnosticEventPiece(L, os.str());
292    }
293
294    return NULL;
295  }
296};
297} // end anonymous namespace
298
299static void registerTrackConstraint(BugReporterContext& BRC,
300                                    DefinedSVal Constraint,
301                                    bool Assumption) {
302  BRC.addVisitor(new TrackConstraintBRVisitor(Constraint, Assumption));
303}
304
305void bugreporter::registerTrackNullOrUndefValue(BugReporterContext& BRC,
306                                                const void *data,
307                                                const ExplodedNode* N) {
308
309  const Stmt *S = static_cast<const Stmt*>(data);
310
311  if (!S)
312    return;
313
314  GRStateManager &StateMgr = BRC.getStateManager();
315
316  // Walk through nodes until we get one that matches the statement
317  // exactly.
318  while (N) {
319    const ProgramPoint &pp = N->getLocation();
320    if (const PostStmt *ps = dyn_cast<PostStmt>(&pp)) {
321      if (ps->getStmt() == S)
322        break;
323    }
324    N = *N->pred_begin();
325  }
326
327  if (!N)
328    return;
329
330  const GRState *state = N->getState();
331
332  // Walk through lvalue-to-rvalue conversions.
333  if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(S)) {
334    if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) {
335      const VarRegion *R =
336        StateMgr.getRegionManager().getVarRegion(VD, N->getLocationContext());
337
338      // What did we load?
339      SVal V = state->getSVal(loc::MemRegionVal(R));
340
341      if (isa<loc::ConcreteInt>(V) || isa<nonloc::ConcreteInt>(V)
342          || V.isUndef()) {
343        ::registerFindLastStore(BRC, R, V);
344      }
345    }
346  }
347
348  SVal V = state->getSValAsScalarOrLoc(S);
349
350  // Uncomment this to find cases where we aren't properly getting the
351  // base value that was dereferenced.
352  // assert(!V.isUnknownOrUndef());
353
354  // Is it a symbolic value?
355  if (loc::MemRegionVal *L = dyn_cast<loc::MemRegionVal>(&V)) {
356    const SubRegion *R = cast<SubRegion>(L->getRegion());
357    while (R && !isa<SymbolicRegion>(R)) {
358      R = dyn_cast<SubRegion>(R->getSuperRegion());
359    }
360
361    if (R) {
362      assert(isa<SymbolicRegion>(R));
363      registerTrackConstraint(BRC, loc::MemRegionVal(R), false);
364    }
365  }
366}
367
368void bugreporter::registerFindLastStore(BugReporterContext& BRC,
369                                        const void *data,
370                                        const ExplodedNode* N) {
371
372  const MemRegion *R = static_cast<const MemRegion*>(data);
373
374  if (!R)
375    return;
376
377  const GRState *state = N->getState();
378  SVal V = state->getSVal(R);
379
380  if (V.isUnknown())
381    return;
382
383  BRC.addVisitor(new FindLastStoreBRVisitor(V, R));
384}
385
386
387namespace {
388class NilReceiverVisitor : public BugReporterVisitor {
389public:
390  NilReceiverVisitor() {}
391
392  void Profile(llvm::FoldingSetNodeID &ID) const {
393    static int x = 0;
394    ID.AddPointer(&x);
395  }
396
397  PathDiagnosticPiece* VisitNode(const ExplodedNode *N,
398                                 const ExplodedNode *PrevN,
399                                 BugReporterContext& BRC) {
400
401    const PostStmt *P = N->getLocationAs<PostStmt>();
402    if (!P)
403      return 0;
404    const ObjCMessageExpr *ME = P->getStmtAs<ObjCMessageExpr>();
405    if (!ME)
406      return 0;
407    const Expr *Receiver = ME->getInstanceReceiver();
408    if (!Receiver)
409      return 0;
410    const GRState *state = N->getState();
411    const SVal &V = state->getSVal(Receiver);
412    const DefinedOrUnknownSVal *DV = dyn_cast<DefinedOrUnknownSVal>(&V);
413    if (!DV)
414      return 0;
415    state = state->assume(*DV, true);
416    if (state)
417      return 0;
418
419    // The receiver was nil, and hence the method was skipped.
420    // Register a BugReporterVisitor to issue a message telling us how
421    // the receiver was null.
422    bugreporter::registerTrackNullOrUndefValue(BRC, Receiver, N);
423    // Issue a message saying that the method was skipped.
424    PathDiagnosticLocation L(Receiver, BRC.getSourceManager());
425    return new PathDiagnosticEventPiece(L, "No method actually called "
426                                           "because the receiver is nil");
427  }
428};
429} // end anonymous namespace
430
431void bugreporter::registerNilReceiverVisitor(BugReporterContext &BRC) {
432  BRC.addVisitor(new NilReceiverVisitor());
433}
434
435// Registers every VarDecl inside a Stmt with a last store vistor.
436void bugreporter::registerVarDeclsLastStore(BugReporterContext &BRC,
437                                                   const void *stmt,
438                                                   const ExplodedNode *N) {
439  const Stmt *S = static_cast<const Stmt *>(stmt);
440
441  std::deque<const Stmt *> WorkList;
442
443  WorkList.push_back(S);
444
445  while (!WorkList.empty()) {
446    const Stmt *Head = WorkList.front();
447    WorkList.pop_front();
448
449    GRStateManager &StateMgr = BRC.getStateManager();
450    const GRState *state = N->getState();
451
452    if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(Head)) {
453      if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) {
454        const VarRegion *R =
455        StateMgr.getRegionManager().getVarRegion(VD, N->getLocationContext());
456
457        // What did we load?
458        SVal V = state->getSVal(S);
459
460        if (isa<loc::ConcreteInt>(V) || isa<nonloc::ConcreteInt>(V)) {
461          ::registerFindLastStore(BRC, R, V);
462        }
463      }
464    }
465
466    for (Stmt::const_child_iterator I = Head->child_begin();
467        I != Head->child_end(); ++I)
468      WorkList.push_back(*I);
469  }
470}
471