lib/GR/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 using namespace GR;
  24
  25 //===----------------------------------------------------------------------===//
  26 // Utility functions.
  27 //===----------------------------------------------------------------------===//
  28
  29 const 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
  50 const 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
  57 const 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
  65 const 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
  76 namespace {
  77 class FindLastStoreBRVisitor : public BugReporterVisitor {
  78   const MemRegion *R;
  79   SVal V;
  80   bool satisfied;
  81   const ExplodedNode *StoreSite;
  82 public:
  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
 225 static void registerFindLastStore(BugReporterContext& BRC, const MemRegion *R,
 226                                   SVal V) {
 227   BRC.addVisitor(new FindLastStoreBRVisitor(V, R));
 228 }
 229
 230 class TrackConstraintBRVisitor : public BugReporterVisitor {
 231   DefinedSVal Constraint;
 232   const bool Assumption;
 233   bool isSatisfied;
 234 public:
 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
 301 static void registerTrackConstraint(BugReporterContext& BRC,
 302                                     DefinedSVal Constraint,
 303                                     bool Assumption) {
 304   BRC.addVisitor(new TrackConstraintBRVisitor(Constraint, Assumption));
 305 }
 306
 307 void 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
 355 void 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
 374 namespace {
 375 class NilReceiverVisitor : public BugReporterVisitor {
 376 public:
 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
 418 void bugreporter::registerNilReceiverVisitor(BugReporterContext &BRC) {
 419   BRC.addVisitor(new NilReceiverVisitor());
 420 }
 421
 422 // Registers every VarDecl inside a Stmt with a last store vistor.
 423 void 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 }