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/ProgramState.h"
  23 #include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h"
  24 #include "clang/AST/Type.h"
  25 #include "clang/AST/ExprObjC.h"
  26 #include "clang/AST/ExprCXX.h"
  27 #include "clang/AST/StmtObjC.h"
  28
  29 namespace clang {
  30
  31 class ObjCForCollectionStmt;
  32
  33 namespace ento {
  34
  35 class AnalysisManager;
  36 class CallOrObjCMessage;
  37 class ObjCMessage;
  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   ProgramStateManager 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 ProgramState *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   /// Whether or not GC is enabled in this analysis.
  78   bool ObjCGCEnabled;
  79
  80   /// The BugReporter associated with this engine.  It is important that
  81   ///  this object be placed at the very end of member variables so that its
  82   ///  destructor is called before the rest of the ExprEngine is destroyed.
  83   GRBugReporter BR;
  84
  85 public:
  86   ExprEngine(AnalysisManager &mgr, bool gcEnabled);
  87
  88   ~ExprEngine();
  89
  90   void ExecuteWorkList(const LocationContext *L, unsigned Steps = 150000) {
  91     Engine.ExecuteWorkList(L, Steps, 0);
  92   }
  93
  94   /// Execute the work list with an initial state. Nodes that reaches the exit
  95   /// of the function are added into the Dst set, which represent the exit
  96   /// state of the function call.
  97   void ExecuteWorkListWithInitialState(const LocationContext *L, unsigned Steps,
  98                                        const ProgramState *InitState,
  99                                        ExplodedNodeSet &Dst) {
 100     Engine.ExecuteWorkListWithInitialState(L, Steps, InitState, Dst);
 101   }
 102
 103   /// getContext - Return the ASTContext associated with this analysis.
 104   ASTContext &getContext() const { return AMgr.getASTContext(); }
 105
 106   virtual AnalysisManager &getAnalysisManager() { return AMgr; }
 107
 108   CheckerManager &getCheckerManager() const {
 109     return *AMgr.getCheckerManager();
 110   }
 111
 112   SValBuilder &getSValBuilder() { return svalBuilder; }
 113
 114   BugReporter& getBugReporter() { return BR; }
 115
 116   StmtNodeBuilder &getBuilder() { assert(Builder); return *Builder; }
 117
 118   bool isObjCGCEnabled() { return ObjCGCEnabled; }
 119
 120   /// ViewGraph - Visualize the ExplodedGraph created by executing the
 121   ///  simulation.
 122   void ViewGraph(bool trim = false);
 123
 124   void ViewGraph(ExplodedNode** Beg, ExplodedNode** End);
 125
 126   /// getInitialState - Return the initial state used for the root vertex
 127   ///  in the ExplodedGraph.
 128   const ProgramState *getInitialState(const LocationContext *InitLoc);
 129
 130   ExplodedGraph& getGraph() { return G; }
 131   const ExplodedGraph& getGraph() const { return G; }
 132
 133   /// processCFGElement - Called by CoreEngine. Used to generate new successor
 134   ///  nodes by processing the 'effects' of a CFG element.
 135   void processCFGElement(const CFGElement E, StmtNodeBuilder& builder);
 136
 137   void ProcessStmt(const CFGStmt S, StmtNodeBuilder &builder);
 138
 139   void ProcessInitializer(const CFGInitializer I, StmtNodeBuilder &builder);
 140
 141   void ProcessImplicitDtor(const CFGImplicitDtor D, StmtNodeBuilder &builder);
 142
 143   void ProcessAutomaticObjDtor(const CFGAutomaticObjDtor D,
 144                             StmtNodeBuilder &builder);
 145   void ProcessBaseDtor(const CFGBaseDtor D, StmtNodeBuilder &builder);
 146   void ProcessMemberDtor(const CFGMemberDtor D, StmtNodeBuilder &builder);
 147   void ProcessTemporaryDtor(const CFGTemporaryDtor D,
 148                             StmtNodeBuilder &builder);
 149
 150   /// Called by CoreEngine when processing the entrance of a CFGBlock.
 151   virtual void processCFGBlockEntrance(ExplodedNodeSet &dstNodes,
 152                                 GenericNodeBuilder<BlockEntrance> &nodeBuilder);
 153
 154   /// ProcessBranch - Called by CoreEngine.  Used to generate successor
 155   ///  nodes by processing the 'effects' of a branch condition.
 156   void processBranch(const Stmt *Condition, const Stmt *Term,
 157                      BranchNodeBuilder& builder);
 158
 159   /// processIndirectGoto - Called by CoreEngine.  Used to generate successor
 160   ///  nodes by processing the 'effects' of a computed goto jump.
 161   void processIndirectGoto(IndirectGotoNodeBuilder& builder);
 162
 163   /// ProcessSwitch - Called by CoreEngine.  Used to generate successor
 164   ///  nodes by processing the 'effects' of a switch statement.
 165   void processSwitch(SwitchNodeBuilder& builder);
 166
 167   /// ProcessEndPath - Called by CoreEngine.  Used to generate end-of-path
 168   ///  nodes when the control reaches the end of a function.
 169   void processEndOfFunction(EndOfFunctionNodeBuilder& builder);
 170
 171   /// Generate the entry node of the callee.
 172   void processCallEnter(CallEnterNodeBuilder &builder);
 173
 174   /// Generate the first post callsite node.
 175   void processCallExit(CallExitNodeBuilder &builder);
 176
 177   /// Called by CoreEngine when the analysis worklist has terminated.
 178   void processEndWorklist(bool hasWorkRemaining);
 179
 180   /// evalAssume - Callback function invoked by the ConstraintManager when
 181   ///  making assumptions about state values.
 182   const ProgramState *processAssume(const ProgramState *state, SVal cond,bool assumption);
 183
 184   /// wantsRegionChangeUpdate - Called by ProgramStateManager to determine if a
 185   ///  region change should trigger a processRegionChanges update.
 186   bool wantsRegionChangeUpdate(const ProgramState *state);
 187
 188   /// processRegionChanges - Called by ProgramStateManager whenever a change is made
 189   ///  to the store. Used to update checkers that track region values.
 190   const ProgramState *
 191   processRegionChanges(const ProgramState *state,
 192                        const StoreManager::InvalidatedSymbols *invalidated,
 193                        ArrayRef<const MemRegion *> ExplicitRegions,
 194                        ArrayRef<const MemRegion *> Regions);
 195
 196   /// printState - Called by ProgramStateManager to print checker-specific data.
 197   void printState(raw_ostream &Out, const ProgramState *State,
 198                   const char *NL, const char *Sep);
 199
 200   virtual ProgramStateManager& getStateManager() { return StateMgr; }
 201
 202   StoreManager& getStoreManager() { return StateMgr.getStoreManager(); }
 203
 204   ConstraintManager& getConstraintManager() {
 205     return StateMgr.getConstraintManager();
 206   }
 207
 208   // FIXME: Remove when we migrate over to just using SValBuilder.
 209   BasicValueFactory& getBasicVals() {
 210     return StateMgr.getBasicVals();
 211   }
 212   const BasicValueFactory& getBasicVals() const {
 213     return StateMgr.getBasicVals();
 214   }
 215
 216   // FIXME: Remove when we migrate over to just using ValueManager.
 217   SymbolManager& getSymbolManager() { return SymMgr; }
 218   const SymbolManager& getSymbolManager() const { return SymMgr; }
 219
 220   // Functions for external checking of whether we have unfinished work
 221   bool wasBlocksExhausted() const { return Engine.wasBlocksExhausted(); }
 222   bool hasEmptyWorkList() const { return !Engine.getWorkList()->hasWork(); }
 223   bool hasWorkRemaining() const { return Engine.hasWorkRemaining(); }
 224
 225   const CoreEngine &getCoreEngine() const { return Engine; }
 226
 227 public:
 228   ExplodedNode *MakeNode(ExplodedNodeSet &Dst, const Stmt *S,
 229                          ExplodedNode *Pred, const ProgramState *St,
 230                          ProgramPoint::Kind K = ProgramPoint::PostStmtKind,
 231                          const ProgramPointTag *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   /// Transfer function logic for computing the lvalue of an Objective-C ivar.
 304   void VisitLvalObjCIvarRefExpr(const ObjCIvarRefExpr *DR, ExplodedNode *Pred,
 305                                 ExplodedNodeSet &Dst);
 306
 307   /// VisitObjCForCollectionStmt - Transfer function logic for
 308   ///  ObjCForCollectionStmt.
 309   void VisitObjCForCollectionStmt(const ObjCForCollectionStmt *S,
 310                                   ExplodedNode *Pred, ExplodedNodeSet &Dst);
 311
 312   void VisitObjCMessage(const ObjCMessage &msg, ExplodedNode *Pred,
 313                         ExplodedNodeSet &Dst);
 314
 315   /// VisitReturnStmt - Transfer function logic for return statements.
 316   void VisitReturnStmt(const ReturnStmt *R, ExplodedNode *Pred,
 317                        ExplodedNodeSet &Dst);
 318
 319   /// VisitOffsetOfExpr - Transfer function for offsetof.
 320   void VisitOffsetOfExpr(const OffsetOfExpr *Ex, ExplodedNode *Pred,
 321                          ExplodedNodeSet &Dst);
 322
 323   /// VisitUnaryExprOrTypeTraitExpr - Transfer function for sizeof.
 324   void VisitUnaryExprOrTypeTraitExpr(const UnaryExprOrTypeTraitExpr *Ex,
 325                               ExplodedNode *Pred, ExplodedNodeSet &Dst);
 326
 327   /// VisitUnaryOperator - Transfer function logic for unary operators.
 328   void VisitUnaryOperator(const UnaryOperator* B, ExplodedNode *Pred,
 329                           ExplodedNodeSet &Dst);
 330
 331   void VisitCXXThisExpr(const CXXThisExpr *TE, ExplodedNode *Pred,
 332                         ExplodedNodeSet & Dst);
 333
 334   void VisitCXXTemporaryObjectExpr(const CXXTemporaryObjectExpr *expr,
 335                                    ExplodedNode *Pred, ExplodedNodeSet &Dst) {
 336     VisitCXXConstructExpr(expr, 0, Pred, Dst);
 337   }
 338
 339   void VisitCXXConstructExpr(const CXXConstructExpr *E, const MemRegion *Dest,
 340                              ExplodedNode *Pred, ExplodedNodeSet &Dst);
 341
 342   void VisitCXXDestructor(const CXXDestructorDecl *DD,
 343                           const MemRegion *Dest, const Stmt *S,
 344                           ExplodedNode *Pred, ExplodedNodeSet &Dst);
 345
 346   void VisitCXXNewExpr(const CXXNewExpr *CNE, ExplodedNode *Pred,
 347                        ExplodedNodeSet &Dst);
 348
 349   void VisitCXXDeleteExpr(const CXXDeleteExpr *CDE, ExplodedNode *Pred,
 350                           ExplodedNodeSet &Dst);
 351
 352   void VisitAggExpr(const Expr *E, const MemRegion *Dest, ExplodedNode *Pred,
 353                     ExplodedNodeSet &Dst);
 354
 355   /// Create a C++ temporary object for an rvalue.
 356   void CreateCXXTemporaryObject(const MaterializeTemporaryExpr *ME,
 357                                 ExplodedNode *Pred,
 358                                 ExplodedNodeSet &Dst);
 359
 360   /// Synthesize CXXThisRegion.
 361   const CXXThisRegion *getCXXThisRegion(const CXXRecordDecl *RD,
 362                                         const StackFrameContext *SFC);
 363
 364   const CXXThisRegion *getCXXThisRegion(const CXXMethodDecl *decl,
 365                                         const StackFrameContext *frameCtx);
 366
 367   /// Evaluate arguments with a work list algorithm.
 368   void evalArguments(ConstExprIterator AI, ConstExprIterator AE,
 369                      const FunctionProtoType *FnType,
 370                      ExplodedNode *Pred, ExplodedNodeSet &Dst,
 371                      bool FstArgAsLValue = false);
 372
 373   /// Evaluate callee expression (for a function call).
 374   void evalCallee(const CallExpr *callExpr, const ExplodedNodeSet &src,
 375                   ExplodedNodeSet &dest);
 376
 377   /// evalEagerlyAssume - Given the nodes in 'Src', eagerly assume symbolic
 378   ///  expressions of the form 'x != 0' and generate new nodes (stored in Dst)
 379   ///  with those assumptions.
 380   void evalEagerlyAssume(ExplodedNodeSet &Dst, ExplodedNodeSet &Src,
 381                          const Expr *Ex);
 382
 383   std::pair<const ProgramPointTag *, const ProgramPointTag*>
 384     getEagerlyAssumeTags();
 385
 386   SVal evalMinus(SVal X) {
 387     return X.isValid() ? svalBuilder.evalMinus(cast<NonLoc>(X)) : X;
 388   }
 389
 390   SVal evalComplement(SVal X) {
 391     return X.isValid() ? svalBuilder.evalComplement(cast<NonLoc>(X)) : X;
 392   }
 393
 394 public:
 395
 396   SVal evalBinOp(const ProgramState *state, BinaryOperator::Opcode op,
 397                  NonLoc L, NonLoc R, QualType T) {
 398     return svalBuilder.evalBinOpNN(state, op, L, R, T);
 399   }
 400
 401   SVal evalBinOp(const ProgramState *state, BinaryOperator::Opcode op,
 402                  NonLoc L, SVal R, QualType T) {
 403     return R.isValid() ? svalBuilder.evalBinOpNN(state,op,L, cast<NonLoc>(R), T) : R;
 404   }
 405
 406   SVal evalBinOp(const ProgramState *ST, BinaryOperator::Opcode Op,
 407                  SVal LHS, SVal RHS, QualType T) {
 408     return svalBuilder.evalBinOp(ST, Op, LHS, RHS, T);
 409   }
 410
 411 protected:
 412   void evalObjCMessage(ExplodedNodeSet &Dst, const ObjCMessage &msg,
 413                        ExplodedNode *Pred, const ProgramState *state);
 414
 415   const ProgramState *invalidateArguments(const ProgramState *State,
 416                                           const CallOrObjCMessage &Call,
 417                                           const LocationContext *LC);
 418
 419   const ProgramState *MarkBranch(const ProgramState *St, const Stmt *Terminator,
 420                             bool branchTaken);
 421
 422   /// evalBind - Handle the semantics of binding a value to a specific location.
 423   ///  This method is used by evalStore, VisitDeclStmt, and others.
 424   void evalBind(ExplodedNodeSet &Dst, const Stmt *StoreE, ExplodedNode *Pred,
 425                 SVal location, SVal Val, bool atDeclInit = false);
 426
 427 public:
 428   // FIXME: 'tag' should be removed, and a LocationContext should be used
 429   // instead.
 430   // FIXME: Comment on the meaning of the arguments, when 'St' may not
 431   // be the same as Pred->state, and when 'location' may not be the
 432   // same as state->getLValue(Ex).
 433   /// Simulate a read of the result of Ex.
 434   void evalLoad(ExplodedNodeSet &Dst, const Expr *Ex, ExplodedNode *Pred,
 435                 const ProgramState *St, SVal location, const ProgramPointTag *tag = 0,
 436                 QualType LoadTy = QualType());
 437
 438   // FIXME: 'tag' should be removed, and a LocationContext should be used
 439   // instead.
 440   void evalStore(ExplodedNodeSet &Dst, const Expr *AssignE, const Expr *StoreE,
 441                  ExplodedNode *Pred, const ProgramState *St, SVal TargetLV, SVal Val,
 442                  const ProgramPointTag *tag = 0);
 443 private:
 444   void evalLoadCommon(ExplodedNodeSet &Dst, const Expr *Ex, ExplodedNode *Pred,
 445                       const ProgramState *St, SVal location, const ProgramPointTag *tag,
 446                       QualType LoadTy);
 447
 448   // FIXME: 'tag' should be removed, and a LocationContext should be used
 449   // instead.
 450   void evalLocation(ExplodedNodeSet &Dst, const Stmt *S, ExplodedNode *Pred,
 451                     const ProgramState *St, SVal location,
 452                     const ProgramPointTag *tag, bool isLoad);
 453
 454   bool InlineCall(ExplodedNodeSet &Dst, const CallExpr *CE, ExplodedNode *Pred);
 455
 456
 457 public:
 458   /// Returns true if calling the specific function or method would possibly
 459   /// cause global variables to be invalidated.
 460   bool doesInvalidateGlobals(const CallOrObjCMessage &callOrMessage) const;
 461
 462 };
 463
 464 } // end ento namespace
 465
 466 } // end clang namespace
 467
 468 #endif