lib/Checker/BugReporterVisitors.cpp

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