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