contrib/llvm/tools/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h

   1 //===-- ExprEngine.h - Path-Sensitive Expression-Level Dataflow ---*- 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 meta-engine for path-sensitive dataflow analysis that
  11 //  is built on CoreEngine, but provides the boilerplate to execute transfer
  12 //  functions and build the ExplodedGraph at the expression level.
  13 //
  14 //===----------------------------------------------------------------------===//
  15
  16 #ifndef LLVM_CLANG_GR_EXPRENGINE
  17 #define LLVM_CLANG_GR_EXPRENGINE
  18
  19 #include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h"
  20 #include "clang/StaticAnalyzer/Core/PathSensitive/SubEngine.h"
  21 #include "clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h"
  22 #include "clang/StaticAnalyzer/Core/PathSensitive/GRState.h"
  23 #include "clang/StaticAnalyzer/Core/PathSensitive/TransferFuncs.h"
  24 #include "clang/StaticAnalyzer/Core/PathSensitive/ObjCMessage.h"
  25 #include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h"
  26 #include "clang/AST/Type.h"
  27 #include "clang/AST/ExprObjC.h"
  28 #include "clang/AST/ExprCXX.h"
  29 #include "clang/AST/StmtObjC.h"
  30
  31 namespace clang {
  32
  33 class ObjCForCollectionStmt;
  34
  35 namespace ento {
  36
  37 class AnalysisManager;
  38
  39 class ExprEngine : public SubEngine {
  40   AnalysisManager &AMgr;
  41
  42   CoreEngine Engine;
  43
  44   /// G - the simulation graph.
  45   ExplodedGraph& G;
  46
  47   /// Builder - The current StmtNodeBuilder which is used when building the
  48   ///  nodes for a given statement.
  49   StmtNodeBuilder* Builder;
  50
  51   /// StateMgr - Object that manages the data for all created states.
  52   GRStateManager StateMgr;
  53
  54   /// SymMgr - Object that manages the symbol information.
  55   SymbolManager& SymMgr;
  56
  57   /// svalBuilder - SValBuilder object that creates SVals from expressions.
  58   SValBuilder &svalBuilder;
  59
  60   /// EntryNode - The immediate predecessor node.
  61   ExplodedNode* EntryNode;
  62
  63   /// CleanedState - The state for EntryNode "cleaned" of all dead
  64   ///  variables and symbols (as determined by a liveness analysis).
  65   const GRState* CleanedState;
  66
  67   /// currentStmt - The current block-level statement.
  68   const Stmt* currentStmt;
  69
  70   // Obj-C Class Identifiers.
  71   IdentifierInfo* NSExceptionII;
  72
  73   // Obj-C Selectors.
  74   Selector* NSExceptionInstanceRaiseSelectors;
  75   Selector RaiseSel;
  76
  77   /// The BugReporter associated with this engine.  It is important that
  78   ///  this object be placed at the very end of member variables so that its
  79   ///  destructor is called before the rest of the ExprEngine is destroyed.
  80   GRBugReporter BR;
  81
  82   llvm::OwningPtr<TransferFuncs> TF;
  83
  84 public:
  85   ExprEngine(AnalysisManager &mgr, TransferFuncs *tf);
  86
  87   ~ExprEngine();
  88
  89   void ExecuteWorkList(const LocationContext *L, unsigned Steps = 150000) {
  90     Engine.ExecuteWorkList(L, Steps, 0);
  91   }
  92
  93   /// Execute the work list with an initial state. Nodes that reaches the exit
  94   /// of the function are added into the Dst set, which represent the exit
  95   /// state of the function call.
  96   void ExecuteWorkListWithInitialState(const LocationContext *L, unsigned Steps,
  97                                        const GRState *InitState,
  98                                        ExplodedNodeSet &Dst) {
  99     Engine.ExecuteWorkListWithInitialState(L, Steps, InitState, Dst);
 100   }
 101
 102   /// getContext - Return the ASTContext associated with this analysis.
 103   ASTContext& getContext() const { return AMgr.getASTContext(); }
 104
 105   virtual AnalysisManager &getAnalysisManager() { return AMgr; }
 106
 107   CheckerManager &getCheckerManager() const {
 108     return *AMgr.getCheckerManager();
 109   }
 110
 111   SValBuilder &getSValBuilder() { return svalBuilder; }
 112
 113   TransferFuncs& getTF() { return *TF; }
 114
 115   BugReporter& getBugReporter() { return BR; }
 116
 117   StmtNodeBuilder &getBuilder() { assert(Builder); return *Builder; }
 118
 119   // FIXME: Remove once TransferFuncs is no longer referenced.
 120   void setTransferFunction(TransferFuncs* tf);
 121
 122   /// ViewGraph - Visualize the ExplodedGraph created by executing the
 123   ///  simulation.
 124   void ViewGraph(bool trim = false);
 125
 126   void ViewGraph(ExplodedNode** Beg, ExplodedNode** End);
 127
 128   /// getInitialState - Return the initial state used for the root vertex
 129   ///  in the ExplodedGraph.
 130   const GRState* getInitialState(const LocationContext *InitLoc);
 131
 132   ExplodedGraph& getGraph() { return G; }
 133   const ExplodedGraph& getGraph() const { return G; }
 134
 135   /// processCFGElement - Called by CoreEngine. Used to generate new successor
 136   ///  nodes by processing the 'effects' of a CFG element.
 137   void processCFGElement(const CFGElement E, StmtNodeBuilder& builder);
 138
 139   void ProcessStmt(const CFGStmt S, StmtNodeBuilder &builder);
 140
 141   void ProcessInitializer(const CFGInitializer I, StmtNodeBuilder &builder);
 142
 143   void ProcessImplicitDtor(const CFGImplicitDtor D, StmtNodeBuilder &builder);
 144
 145   void ProcessAutomaticObjDtor(const CFGAutomaticObjDtor D,
 146                             StmtNodeBuilder &builder);
 147   void ProcessBaseDtor(const CFGBaseDtor D, StmtNodeBuilder &builder);
 148   void ProcessMemberDtor(const CFGMemberDtor D, StmtNodeBuilder &builder);
 149   void ProcessTemporaryDtor(const CFGTemporaryDtor D,
 150                             StmtNodeBuilder &builder);
 151
 152   /// Called by CoreEngine when processing the entrance of a CFGBlock.
 153   virtual void processCFGBlockEntrance(ExplodedNodeSet &dstNodes,
 154                                 GenericNodeBuilder<BlockEntrance> &nodeBuilder);
 155
 156   /// ProcessBranch - Called by CoreEngine.  Used to generate successor
 157   ///  nodes by processing the 'effects' of a branch condition.
 158   void processBranch(const Stmt* Condition, const Stmt* Term,
 159                      BranchNodeBuilder& builder);
 160
 161   /// processIndirectGoto - Called by CoreEngine.  Used to generate successor
 162   ///  nodes by processing the 'effects' of a computed goto jump.
 163   void processIndirectGoto(IndirectGotoNodeBuilder& builder);
 164
 165   /// ProcessSwitch - Called by CoreEngine.  Used to generate successor
 166   ///  nodes by processing the 'effects' of a switch statement.
 167   void processSwitch(SwitchNodeBuilder& builder);
 168
 169   /// ProcessEndPath - Called by CoreEngine.  Used to generate end-of-path
 170   ///  nodes when the control reaches the end of a function.
 171   void processEndOfFunction(EndOfFunctionNodeBuilder& builder);
 172
 173   /// Generate the entry node of the callee.
 174   void processCallEnter(CallEnterNodeBuilder &builder);
 175
 176   /// Generate the first post callsite node.
 177   void processCallExit(CallExitNodeBuilder &builder);
 178
 179   /// Called by CoreEngine when the analysis worklist has terminated.
 180   void processEndWorklist(bool hasWorkRemaining);
 181
 182   /// evalAssume - Callback function invoked by the ConstraintManager when
 183   ///  making assumptions about state values.
 184   const GRState *processAssume(const GRState *state, SVal cond,bool assumption);
 185
 186   /// wantsRegionChangeUpdate - Called by GRStateManager to determine if a
 187   ///  region change should trigger a processRegionChanges update.
 188   bool wantsRegionChangeUpdate(const GRState* state);
 189
 190   /// processRegionChanges - Called by GRStateManager whenever a change is made
 191   ///  to the store. Used to update checkers that track region values.
 192   const GRState *
 193   processRegionChanges(const GRState *state,
 194                        const StoreManager::InvalidatedSymbols *invalidated,
 195                        const MemRegion * const *Begin,
 196                        const MemRegion * const *End);
 197
 198   virtual GRStateManager& getStateManager() { return StateMgr; }
 199
 200   StoreManager& getStoreManager() { return StateMgr.getStoreManager(); }
 201
 202   ConstraintManager& getConstraintManager() {
 203     return StateMgr.getConstraintManager();
 204   }
 205
 206   // FIXME: Remove when we migrate over to just using SValBuilder.
 207   BasicValueFactory& getBasicVals() {
 208     return StateMgr.getBasicVals();
 209   }
 210   const BasicValueFactory& getBasicVals() const {
 211     return StateMgr.getBasicVals();
 212   }
 213
 214   // FIXME: Remove when we migrate over to just using ValueManager.
 215   SymbolManager& getSymbolManager() { return SymMgr; }
 216   const SymbolManager& getSymbolManager() const { return SymMgr; }
 217
 218   // Functions for external checking of whether we have unfinished work
 219   bool wasBlocksExhausted() const { return Engine.wasBlocksExhausted(); }
 220   bool hasEmptyWorkList() const { return !Engine.getWorkList()->hasWork(); }
 221   bool hasWorkRemaining() const { return Engine.hasWorkRemaining(); }
 222
 223   const CoreEngine &getCoreEngine() const { return Engine; }
 224
 225 protected:
 226   const GRState* GetState(ExplodedNode* N) {
 227     return N == EntryNode ? CleanedState : N->getState();
 228   }
 229
 230 public:
 231   ExplodedNode* MakeNode(ExplodedNodeSet& Dst, const Stmt* S,
 232                          ExplodedNode* Pred, const GRState* St,
 233                          ProgramPoint::Kind K = ProgramPoint::PostStmtKind,
 234                          const void *tag = 0);
 235
 236   /// Visit - Transfer function logic for all statements.  Dispatches to
 237   ///  other functions that handle specific kinds of statements.
 238   void Visit(const Stmt* S, ExplodedNode* Pred, ExplodedNodeSet& Dst);
 239
 240   /// VisitArraySubscriptExpr - Transfer function for array accesses.
 241   void VisitLvalArraySubscriptExpr(const ArraySubscriptExpr* Ex,
 242                                    ExplodedNode* Pred,
 243                                    ExplodedNodeSet& Dst);
 244
 245   /// VisitAsmStmt - Transfer function logic for inline asm.
 246   void VisitAsmStmt(const AsmStmt* A, ExplodedNode* Pred, ExplodedNodeSet& Dst);
 247
 248   void VisitAsmStmtHelperOutputs(const AsmStmt* A,
 249                                  AsmStmt::const_outputs_iterator I,
 250                                  AsmStmt::const_outputs_iterator E,
 251                                  ExplodedNode* Pred, ExplodedNodeSet& Dst);
 252
 253   void VisitAsmStmtHelperInputs(const AsmStmt* A,
 254                                 AsmStmt::const_inputs_iterator I,
 255                                 AsmStmt::const_inputs_iterator E,
 256                                 ExplodedNode* Pred, ExplodedNodeSet& Dst);
 257
 258   /// VisitBlockExpr - Transfer function logic for BlockExprs.
 259   void VisitBlockExpr(const BlockExpr *BE, ExplodedNode *Pred,
 260                       ExplodedNodeSet &Dst);
 261
 262   /// VisitBinaryOperator - Transfer function logic for binary operators.
 263   void VisitBinaryOperator(const BinaryOperator* B, ExplodedNode* Pred,
 264                            ExplodedNodeSet& Dst);
 265
 266
 267   /// VisitCall - Transfer function for function calls.
 268   void VisitCallExpr(const CallExpr* CE, ExplodedNode* Pred,
 269                      ExplodedNodeSet& Dst);
 270
 271   /// VisitCast - Transfer function logic for all casts (implicit and explicit).
 272   void VisitCast(const CastExpr *CastE, const Expr *Ex, ExplodedNode *Pred,
 273                 ExplodedNodeSet &Dst);
 274
 275   /// VisitCompoundLiteralExpr - Transfer function logic for compound literals.
 276   void VisitCompoundLiteralExpr(const CompoundLiteralExpr* CL,
 277                                 ExplodedNode* Pred, ExplodedNodeSet& Dst);
 278
 279   /// Transfer function logic for DeclRefExprs and BlockDeclRefExprs.
 280   void VisitCommonDeclRefExpr(const Expr* DR, const NamedDecl *D,
 281                               ExplodedNode* Pred, ExplodedNodeSet& Dst);
 282
 283   /// VisitDeclStmt - Transfer function logic for DeclStmts.
 284   void VisitDeclStmt(const DeclStmt* DS, ExplodedNode* Pred,
 285                      ExplodedNodeSet& Dst);
 286
 287   /// VisitGuardedExpr - Transfer function logic for ?, __builtin_choose
 288   void VisitGuardedExpr(const Expr* Ex, const Expr* L, const Expr* R,
 289                         ExplodedNode* Pred, ExplodedNodeSet& Dst);
 290
 291   void VisitInitListExpr(const InitListExpr* E, ExplodedNode* Pred,
 292                          ExplodedNodeSet& Dst);
 293
 294   /// VisitLogicalExpr - Transfer function logic for '&&', '||'
 295   void VisitLogicalExpr(const BinaryOperator* B, ExplodedNode* Pred,
 296                         ExplodedNodeSet& Dst);
 297
 298   /// VisitMemberExpr - Transfer function for member expressions.
 299   void VisitMemberExpr(const MemberExpr* M, ExplodedNode* Pred,
 300                            ExplodedNodeSet& Dst);
 301
 302   /// Transfer function logic for ObjCAtSynchronizedStmts.
 303   void VisitObjCAtSynchronizedStmt(const ObjCAtSynchronizedStmt *S,
 304                                    ExplodedNode *Pred, ExplodedNodeSet &Dst);
 305
 306   void VisitObjCPropertyRefExpr(const ObjCPropertyRefExpr *E,
 307                                 ExplodedNode *Pred, ExplodedNodeSet &Dst);
 308
 309   /// Transfer function logic for computing the lvalue of an Objective-C ivar.
 310   void VisitLvalObjCIvarRefExpr(const ObjCIvarRefExpr* DR, ExplodedNode* Pred,
 311                                 ExplodedNodeSet& Dst);
 312
 313   /// VisitObjCForCollectionStmt - Transfer function logic for
 314   ///  ObjCForCollectionStmt.
 315   void VisitObjCForCollectionStmt(const ObjCForCollectionStmt* S,
 316                                   ExplodedNode* Pred, ExplodedNodeSet& Dst);
 317
 318   void VisitObjCForCollectionStmtAux(const ObjCForCollectionStmt* S,
 319                                      ExplodedNode* Pred,
 320                                      ExplodedNodeSet& Dst, SVal ElementV);
 321
 322   /// VisitObjCMessageExpr - Transfer function for ObjC message expressions.
 323   void VisitObjCMessageExpr(const ObjCMessageExpr* ME, ExplodedNode* Pred,
 324                             ExplodedNodeSet& Dst);
 325   void VisitObjCMessage(const ObjCMessage &msg, ExplodedNodeSet &Src,
 326                         ExplodedNodeSet& Dst);
 327
 328   /// VisitReturnStmt - Transfer function logic for return statements.
 329   void VisitReturnStmt(const ReturnStmt* R, ExplodedNode* Pred,
 330                        ExplodedNodeSet& Dst);
 331
 332   /// VisitOffsetOfExpr - Transfer function for offsetof.
 333   void VisitOffsetOfExpr(const OffsetOfExpr* Ex, ExplodedNode* Pred,
 334                          ExplodedNodeSet& Dst);
 335
 336   /// VisitUnaryExprOrTypeTraitExpr - Transfer function for sizeof.
 337   void VisitUnaryExprOrTypeTraitExpr(const UnaryExprOrTypeTraitExpr* Ex,
 338                               ExplodedNode* Pred, ExplodedNodeSet& Dst);
 339
 340   /// VisitUnaryOperator - Transfer function logic for unary operators.
 341   void VisitUnaryOperator(const UnaryOperator* B, ExplodedNode* Pred,
 342                           ExplodedNodeSet& Dst);
 343
 344   void VisitCXXThisExpr(const CXXThisExpr *TE, ExplodedNode *Pred,
 345                         ExplodedNodeSet & Dst);
 346
 347   void VisitCXXTemporaryObjectExpr(const CXXTemporaryObjectExpr *expr,
 348                                    ExplodedNode *Pred, ExplodedNodeSet &Dst) {
 349     VisitCXXConstructExpr(expr, 0, Pred, Dst);
 350   }
 351
 352   void VisitCXXConstructExpr(const CXXConstructExpr *E, const MemRegion *Dest,
 353                              ExplodedNode *Pred, ExplodedNodeSet &Dst);
 354
 355   void VisitCXXDestructor(const CXXDestructorDecl *DD,
 356                           const MemRegion *Dest, const Stmt *S,
 357                           ExplodedNode *Pred, ExplodedNodeSet &Dst);
 358
 359   void VisitCXXNewExpr(const CXXNewExpr *CNE, ExplodedNode *Pred,
 360                        ExplodedNodeSet &Dst);
 361
 362   void VisitCXXDeleteExpr(const CXXDeleteExpr *CDE, ExplodedNode *Pred,
 363                           ExplodedNodeSet &Dst);
 364
 365   void VisitAggExpr(const Expr *E, const MemRegion *Dest, ExplodedNode *Pred,
 366                     ExplodedNodeSet &Dst);
 367
 368   /// Create a C++ temporary object for an rvalue.
 369   void CreateCXXTemporaryObject(const Expr *Ex, ExplodedNode *Pred,
 370                                 ExplodedNodeSet &Dst);
 371
 372   /// Synthesize CXXThisRegion.
 373   const CXXThisRegion *getCXXThisRegion(const CXXRecordDecl *RD,
 374                                         const StackFrameContext *SFC);
 375
 376   const CXXThisRegion *getCXXThisRegion(const CXXMethodDecl *decl,
 377                                         const StackFrameContext *frameCtx);
 378
 379   /// Evaluate arguments with a work list algorithm.
 380   void evalArguments(ConstExprIterator AI, ConstExprIterator AE,
 381                      const FunctionProtoType *FnType,
 382                      ExplodedNode *Pred, ExplodedNodeSet &Dst,
 383                      bool FstArgAsLValue = false);
 384
 385   /// Evaluate callee expression (for a function call).
 386   void evalCallee(const CallExpr *callExpr, const ExplodedNodeSet &src,
 387                   ExplodedNodeSet &dest);
 388
 389   /// evalEagerlyAssume - Given the nodes in 'Src', eagerly assume symbolic
 390   ///  expressions of the form 'x != 0' and generate new nodes (stored in Dst)
 391   ///  with those assumptions.
 392   void evalEagerlyAssume(ExplodedNodeSet& Dst, ExplodedNodeSet& Src,
 393                          const Expr *Ex);
 394
 395   SVal evalMinus(SVal X) {
 396     return X.isValid() ? svalBuilder.evalMinus(cast<NonLoc>(X)) : X;
 397   }
 398
 399   SVal evalComplement(SVal X) {
 400     return X.isValid() ? svalBuilder.evalComplement(cast<NonLoc>(X)) : X;
 401   }
 402
 403 public:
 404
 405   SVal evalBinOp(const GRState *state, BinaryOperator::Opcode op,
 406                  NonLoc L, NonLoc R, QualType T) {
 407     return svalBuilder.evalBinOpNN(state, op, L, R, T);
 408   }
 409
 410   SVal evalBinOp(const GRState *state, BinaryOperator::Opcode op,
 411                  NonLoc L, SVal R, QualType T) {
 412     return R.isValid() ? svalBuilder.evalBinOpNN(state,op,L, cast<NonLoc>(R), T) : R;
 413   }
 414
 415   SVal evalBinOp(const GRState *ST, BinaryOperator::Opcode Op,
 416                  SVal LHS, SVal RHS, QualType T) {
 417     return svalBuilder.evalBinOp(ST, Op, LHS, RHS, T);
 418   }
 419
 420 protected:
 421   void evalObjCMessage(ExplodedNodeSet& Dst, const ObjCMessage &msg,
 422                        ExplodedNode* Pred, const GRState *state) {
 423     assert (Builder && "StmtNodeBuilder must be defined.");
 424     getTF().evalObjCMessage(Dst, *this, *Builder, msg, Pred, state);
 425   }
 426
 427   const GRState* MarkBranch(const GRState* St, const Stmt* Terminator,
 428                             bool branchTaken);
 429
 430   /// evalBind - Handle the semantics of binding a value to a specific location.
 431   ///  This method is used by evalStore, VisitDeclStmt, and others.
 432   void evalBind(ExplodedNodeSet& Dst, const Stmt* StoreE, ExplodedNode* Pred,
 433                 const GRState* St, SVal location, SVal Val,
 434                 bool atDeclInit = false);
 435
 436 public:
 437   // FIXME: 'tag' should be removed, and a LocationContext should be used
 438   // instead.
 439   // FIXME: Comment on the meaning of the arguments, when 'St' may not
 440   // be the same as Pred->state, and when 'location' may not be the
 441   // same as state->getLValue(Ex).
 442   /// Simulate a read of the result of Ex.
 443   void evalLoad(ExplodedNodeSet& Dst, const Expr* Ex, ExplodedNode* Pred,
 444                 const GRState* St, SVal location, const void *tag = 0,
 445                 QualType LoadTy = QualType());
 446
 447   // FIXME: 'tag' should be removed, and a LocationContext should be used
 448   // instead.
 449   void evalStore(ExplodedNodeSet& Dst, const Expr* AssignE, const Expr* StoreE,
 450                  ExplodedNode* Pred, const GRState* St, SVal TargetLV, SVal Val,
 451                  const void *tag = 0);
 452 private:
 453   void evalLoadCommon(ExplodedNodeSet& Dst, const Expr* Ex, ExplodedNode* Pred,
 454                       const GRState* St, SVal location, const void *tag,
 455                       QualType LoadTy);
 456
 457   // FIXME: 'tag' should be removed, and a LocationContext should be used
 458   // instead.
 459   void evalLocation(ExplodedNodeSet &Dst, const Stmt *S, ExplodedNode* Pred,
 460                     const GRState* St, SVal location,
 461                     const void *tag, bool isLoad);
 462
 463   bool InlineCall(ExplodedNodeSet &Dst, const CallExpr *CE, ExplodedNode *Pred);
 464
 465
 466 public:
 467   /// Returns true if calling the specific function or method would possibly
 468   /// cause global variables to be invalidated.
 469   bool doesInvalidateGlobals(const CallOrObjCMessage &callOrMessage) const;
 470
 471 };
 472
 473 } // end ento namespace
 474
 475 } // end clang namespace
 476
 477 #endif