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