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_STATICANALYZER_CORE_PATHSENSITIVE_EXPRENGINE_H
  17 #define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_EXPRENGINE_H
  18
  19 #include "clang/AST/Expr.h"
  20 #include "clang/AST/Type.h"
  21 #include "clang/Analysis/CFG.h"
  22 #include "clang/Analysis/DomainSpecific/ObjCNoReturn.h"
  23 #include "clang/Analysis/ProgramPoint.h"
  24 #include "clang/Basic/LLVM.h"
  25 #include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h"
  26 #include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h"
  27 #include "clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h"
  28 #include "clang/StaticAnalyzer/Core/PathSensitive/FunctionSummary.h"
  29 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
  30 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h"
  31 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState_Fwd.h"
  32 #include "clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h"
  33 #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
  34 #include "clang/StaticAnalyzer/Core/PathSensitive/SubEngine.h"
  35 #include "clang/StaticAnalyzer/Core/PathSensitive/WorkList.h"
  36 #include "llvm/ADT/ArrayRef.h"
  37 #include <cassert>
  38 #include <utility>
  39
  40 namespace clang {
  41
  42 class AnalysisDeclContextManager;
  43 class AnalyzerOptions;
  44 class ASTContext;
  45 class ConstructionContext;
  46 class CXXBindTemporaryExpr;
  47 class CXXCatchStmt;
  48 class CXXConstructExpr;
  49 class CXXDeleteExpr;
  50 class CXXNewExpr;
  51 class CXXThisExpr;
  52 class Decl;
  53 class DeclStmt;
  54 class GCCAsmStmt;
  55 class LambdaExpr;
  56 class LocationContext;
  57 class MaterializeTemporaryExpr;
  58 class MSAsmStmt;
  59 class NamedDecl;
  60 class ObjCAtSynchronizedStmt;
  61 class ObjCForCollectionStmt;
  62 class ObjCIvarRefExpr;
  63 class ObjCMessageExpr;
  64 class ReturnStmt;
  65 class Stmt;
  66
  67 namespace cross_tu {
  68
  69 class CrossTranslationUnitContext;
  70
  71 } // namespace cross_tu
  72
  73 namespace ento {
  74
  75 class BasicValueFactory;
  76 class CallEvent;
  77 class CheckerManager;
  78 class ConstraintManager;
  79 class CXXTempObjectRegion;
  80 class MemRegion;
  81 class RegionAndSymbolInvalidationTraits;
  82 class SymbolManager;
  83
  84 class ExprEngine : public SubEngine {
  85 public:
  86   /// The modes of inlining, which override the default analysis-wide settings.
  87   enum InliningModes {
  88     /// Follow the default settings for inlining callees.
  89     Inline_Regular = 0,
  90
  91     /// Do minimal inlining of callees.
  92     Inline_Minimal = 0x1
  93   };
  94
  95   /// Hints for figuring out of a call should be inlined during evalCall().
  96   struct EvalCallOptions {
  97     /// This call is a constructor or a destructor for which we do not currently
  98     /// compute the this-region correctly.
  99     bool IsCtorOrDtorWithImproperlyModeledTargetRegion = false;
 100
 101     /// This call is a constructor or a destructor for a single element within
 102     /// an array, a part of array construction or destruction.
 103     bool IsArrayCtorOrDtor = false;
 104
 105     /// This call is a constructor or a destructor of a temporary value.
 106     bool IsTemporaryCtorOrDtor = false;
 107
 108     /// This call is a constructor for a temporary that is lifetime-extended
 109     /// by binding it to a reference-type field within an aggregate,
 110     /// for example 'A { const C &c; }; A a = { C() };'
 111     bool IsTemporaryLifetimeExtendedViaAggregate = false;
 112
 113     EvalCallOptions() {}
 114   };
 115
 116 private:
 117   cross_tu::CrossTranslationUnitContext &CTU;
 118
 119   AnalysisManager &AMgr;
 120
 121   AnalysisDeclContextManager &AnalysisDeclContexts;
 122
 123   CoreEngine Engine;
 124
 125   /// G - the simulation graph.
 126   ExplodedGraph &G;
 127
 128   /// StateMgr - Object that manages the data for all created states.
 129   ProgramStateManager StateMgr;
 130
 131   /// SymMgr - Object that manages the symbol information.
 132   SymbolManager &SymMgr;
 133
 134   /// svalBuilder - SValBuilder object that creates SVals from expressions.
 135   SValBuilder &svalBuilder;
 136
 137   unsigned int currStmtIdx = 0;
 138   const NodeBuilderContext *currBldrCtx = nullptr;
 139
 140   /// Helper object to determine if an Objective-C message expression
 141   /// implicitly never returns.
 142   ObjCNoReturn ObjCNoRet;
 143
 144   /// Whether or not GC is enabled in this analysis.
 145   bool ObjCGCEnabled;
 146
 147   /// The BugReporter associated with this engine.  It is important that
 148   ///  this object be placed at the very end of member variables so that its
 149   ///  destructor is called before the rest of the ExprEngine is destroyed.
 150   GRBugReporter BR;
 151
 152   /// The functions which have been analyzed through inlining. This is owned by
 153   /// AnalysisConsumer. It can be null.
 154   SetOfConstDecls *VisitedCallees;
 155
 156   /// The flag, which specifies the mode of inlining for the engine.
 157   InliningModes HowToInline;
 158
 159 public:
 160   ExprEngine(cross_tu::CrossTranslationUnitContext &CTU, AnalysisManager &mgr,
 161              bool gcEnabled, SetOfConstDecls *VisitedCalleesIn,
 162              FunctionSummariesTy *FS, InliningModes HowToInlineIn);
 163
 164   ~ExprEngine() override;
 165
 166   /// Returns true if there is still simulation state on the worklist.
 167   bool ExecuteWorkList(const LocationContext *L, unsigned Steps = 150000) {
 168     return Engine.ExecuteWorkList(L, Steps, nullptr);
 169   }
 170
 171   /// Execute the work list with an initial state. Nodes that reaches the exit
 172   /// of the function are added into the Dst set, which represent the exit
 173   /// state of the function call. Returns true if there is still simulation
 174   /// state on the worklist.
 175   bool ExecuteWorkListWithInitialState(const LocationContext *L, unsigned Steps,
 176                                        ProgramStateRef InitState,
 177                                        ExplodedNodeSet &Dst) {
 178     return Engine.ExecuteWorkListWithInitialState(L, Steps, InitState, Dst);
 179   }
 180
 181   /// getContext - Return the ASTContext associated with this analysis.
 182   ASTContext &getContext() const { return AMgr.getASTContext(); }
 183
 184   AnalysisManager &getAnalysisManager() override { return AMgr; }
 185
 186   CheckerManager &getCheckerManager() const {
 187     return *AMgr.getCheckerManager();
 188   }
 189
 190   SValBuilder &getSValBuilder() { return svalBuilder; }
 191
 192   BugReporter &getBugReporter() { return BR; }
 193
 194   cross_tu::CrossTranslationUnitContext *
 195   getCrossTranslationUnitContext() override {
 196     return &CTU;
 197   }
 198
 199   const NodeBuilderContext &getBuilderContext() {
 200     assert(currBldrCtx);
 201     return *currBldrCtx;
 202   }
 203
 204   bool isObjCGCEnabled() { return ObjCGCEnabled; }
 205
 206   const Stmt *getStmt() const;
 207
 208   void GenerateAutoTransition(ExplodedNode *N);
 209   void enqueueEndOfPath(ExplodedNodeSet &S);
 210   void GenerateCallExitNode(ExplodedNode *N);
 211
 212   /// Visualize the ExplodedGraph created by executing the simulation.
 213   void ViewGraph(bool trim = false);
 214
 215   /// Visualize a trimmed ExplodedGraph that only contains paths to the given
 216   /// nodes.
 217   void ViewGraph(ArrayRef<const ExplodedNode *> Nodes);
 218
 219   /// getInitialState - Return the initial state used for the root vertex
 220   ///  in the ExplodedGraph.
 221   ProgramStateRef getInitialState(const LocationContext *InitLoc) override;
 222
 223   ExplodedGraph &getGraph() { return G; }
 224   const ExplodedGraph &getGraph() const { return G; }
 225
 226   /// Run the analyzer's garbage collection - remove dead symbols and
 227   /// bindings from the state.
 228   ///
 229   /// Checkers can participate in this process with two callbacks:
 230   /// \c checkLiveSymbols and \c checkDeadSymbols. See the CheckerDocumentation
 231   /// class for more information.
 232   ///
 233   /// \param Node The predecessor node, from which the processing should start.
 234   /// \param Out The returned set of output nodes.
 235   /// \param ReferenceStmt The statement which is about to be processed.
 236   ///        Everything needed for this statement should be considered live.
 237   ///        A null statement means that everything in child LocationContexts
 238   ///        is dead.
 239   /// \param LC The location context of the \p ReferenceStmt. A null location
 240   ///        context means that we have reached the end of analysis and that
 241   ///        all statements and local variables should be considered dead.
 242   /// \param DiagnosticStmt Used as a location for any warnings that should
 243   ///        occur while removing the dead (e.g. leaks). By default, the
 244   ///        \p ReferenceStmt is used.
 245   /// \param K Denotes whether this is a pre- or post-statement purge. This
 246   ///        must only be ProgramPoint::PostStmtPurgeDeadSymbolsKind if an
 247   ///        entire location context is being cleared, in which case the
 248   ///        \p ReferenceStmt must either be a ReturnStmt or \c NULL. Otherwise,
 249   ///        it must be ProgramPoint::PreStmtPurgeDeadSymbolsKind (the default)
 250   ///        and \p ReferenceStmt must be valid (non-null).
 251   void removeDead(ExplodedNode *Node, ExplodedNodeSet &Out,
 252             const Stmt *ReferenceStmt, const LocationContext *LC,
 253             const Stmt *DiagnosticStmt = nullptr,
 254             ProgramPoint::Kind K = ProgramPoint::PreStmtPurgeDeadSymbolsKind);
 255
 256   /// processCFGElement - Called by CoreEngine. Used to generate new successor
 257   ///  nodes by processing the 'effects' of a CFG element.
 258   void processCFGElement(const CFGElement E, ExplodedNode *Pred,
 259                          unsigned StmtIdx, NodeBuilderContext *Ctx) override;
 260
 261   void ProcessStmt(const Stmt *S, ExplodedNode *Pred);
 262
 263   void ProcessLoopExit(const Stmt* S, ExplodedNode *Pred);
 264
 265   void ProcessInitializer(const CFGInitializer I, ExplodedNode *Pred);
 266
 267   void ProcessImplicitDtor(const CFGImplicitDtor D, ExplodedNode *Pred);
 268
 269   void ProcessNewAllocator(const CXXNewExpr *NE, ExplodedNode *Pred);
 270
 271   void ProcessAutomaticObjDtor(const CFGAutomaticObjDtor D,
 272                                ExplodedNode *Pred, ExplodedNodeSet &Dst);
 273   void ProcessDeleteDtor(const CFGDeleteDtor D,
 274                          ExplodedNode *Pred, ExplodedNodeSet &Dst);
 275   void ProcessBaseDtor(const CFGBaseDtor D,
 276                        ExplodedNode *Pred, ExplodedNodeSet &Dst);
 277   void ProcessMemberDtor(const CFGMemberDtor D,
 278                          ExplodedNode *Pred, ExplodedNodeSet &Dst);
 279   void ProcessTemporaryDtor(const CFGTemporaryDtor D,
 280                             ExplodedNode *Pred, ExplodedNodeSet &Dst);
 281
 282   /// Called by CoreEngine when processing the entrance of a CFGBlock.
 283   void processCFGBlockEntrance(const BlockEdge &L,
 284                                NodeBuilderWithSinks &nodeBuilder,
 285                                ExplodedNode *Pred) override;
 286
 287   /// ProcessBranch - Called by CoreEngine.  Used to generate successor
 288   ///  nodes by processing the 'effects' of a branch condition.
 289   void processBranch(const Stmt *Condition, const Stmt *Term,
 290                      NodeBuilderContext& BuilderCtx,
 291                      ExplodedNode *Pred,
 292                      ExplodedNodeSet &Dst,
 293                      const CFGBlock *DstT,
 294                      const CFGBlock *DstF) override;
 295
 296   /// Called by CoreEngine.
 297   /// Used to generate successor nodes for temporary destructors depending
 298   /// on whether the corresponding constructor was visited.
 299   void processCleanupTemporaryBranch(const CXXBindTemporaryExpr *BTE,
 300                                      NodeBuilderContext &BldCtx,
 301                                      ExplodedNode *Pred, ExplodedNodeSet &Dst,
 302                                      const CFGBlock *DstT,
 303                                      const CFGBlock *DstF) override;
 304
 305   /// Called by CoreEngine.  Used to processing branching behavior
 306   /// at static initializers.
 307   void processStaticInitializer(const DeclStmt *DS,
 308                                 NodeBuilderContext& BuilderCtx,
 309                                 ExplodedNode *Pred,
 310                                 ExplodedNodeSet &Dst,
 311                                 const CFGBlock *DstT,
 312                                 const CFGBlock *DstF) override;
 313
 314   /// processIndirectGoto - Called by CoreEngine.  Used to generate successor
 315   ///  nodes by processing the 'effects' of a computed goto jump.
 316   void processIndirectGoto(IndirectGotoNodeBuilder& builder) override;
 317
 318   /// ProcessSwitch - Called by CoreEngine.  Used to generate successor
 319   ///  nodes by processing the 'effects' of a switch statement.
 320   void processSwitch(SwitchNodeBuilder& builder) override;
 321
 322   /// Called by CoreEngine.  Used to notify checkers that processing a
 323   /// function has begun. Called for both inlined and and top-level functions.
 324   void processBeginOfFunction(NodeBuilderContext &BC,
 325                               ExplodedNode *Pred, ExplodedNodeSet &Dst,
 326                               const BlockEdge &L) override;
 327
 328   /// Called by CoreEngine.  Used to notify checkers that processing a
 329   /// function has ended. Called for both inlined and and top-level functions.
 330   void processEndOfFunction(NodeBuilderContext& BC,
 331                             ExplodedNode *Pred,
 332                             const ReturnStmt *RS = nullptr) override;
 333
 334   /// Remove dead bindings/symbols before exiting a function.
 335   void removeDeadOnEndOfFunction(NodeBuilderContext& BC,
 336                                  ExplodedNode *Pred,
 337                                  ExplodedNodeSet &Dst);
 338
 339   /// Generate the entry node of the callee.
 340   void processCallEnter(NodeBuilderContext& BC, CallEnter CE,
 341                         ExplodedNode *Pred) override;
 342
 343   /// Generate the sequence of nodes that simulate the call exit and the post
 344   /// visit for CallExpr.
 345   void processCallExit(ExplodedNode *Pred) override;
 346
 347   /// Called by CoreEngine when the analysis worklist has terminated.
 348   void processEndWorklist(bool hasWorkRemaining) override;
 349
 350   /// evalAssume - Callback function invoked by the ConstraintManager when
 351   ///  making assumptions about state values.
 352   ProgramStateRef processAssume(ProgramStateRef state, SVal cond,
 353                                 bool assumption) override;
 354
 355   /// processRegionChanges - Called by ProgramStateManager whenever a change is made
 356   ///  to the store. Used to update checkers that track region values.
 357   ProgramStateRef
 358   processRegionChanges(ProgramStateRef state,
 359                        const InvalidatedSymbols *invalidated,
 360                        ArrayRef<const MemRegion *> ExplicitRegions,
 361                        ArrayRef<const MemRegion *> Regions,
 362                        const LocationContext *LCtx,
 363                        const CallEvent *Call) override;
 364
 365   /// printState - Called by ProgramStateManager to print checker-specific data.
 366   void printState(raw_ostream &Out, ProgramStateRef State, const char *NL,
 367                   const char *Sep,
 368                   const LocationContext *LCtx = nullptr) override;
 369
 370   ProgramStateManager &getStateManager() override { return StateMgr; }
 371
 372   StoreManager &getStoreManager() { return StateMgr.getStoreManager(); }
 373
 374   ConstraintManager &getConstraintManager() {
 375     return StateMgr.getConstraintManager();
 376   }
 377
 378   // FIXME: Remove when we migrate over to just using SValBuilder.
 379   BasicValueFactory &getBasicVals() {
 380     return StateMgr.getBasicVals();
 381   }
 382
 383   // FIXME: Remove when we migrate over to just using ValueManager.
 384   SymbolManager &getSymbolManager() { return SymMgr; }
 385   const SymbolManager &getSymbolManager() const { return SymMgr; }
 386
 387   // Functions for external checking of whether we have unfinished work
 388   bool wasBlocksExhausted() const { return Engine.wasBlocksExhausted(); }
 389   bool hasEmptyWorkList() const { return !Engine.getWorkList()->hasWork(); }
 390   bool hasWorkRemaining() const { return Engine.hasWorkRemaining(); }
 391
 392   const CoreEngine &getCoreEngine() const { return Engine; }
 393
 394 public:
 395   /// Visit - Transfer function logic for all statements.  Dispatches to
 396   ///  other functions that handle specific kinds of statements.
 397   void Visit(const Stmt *S, ExplodedNode *Pred, ExplodedNodeSet &Dst);
 398
 399   /// VisitArraySubscriptExpr - Transfer function for array accesses.
 400   void VisitArraySubscriptExpr(const ArraySubscriptExpr *Ex,
 401                                ExplodedNode *Pred,
 402                                ExplodedNodeSet &Dst);
 403
 404   /// VisitGCCAsmStmt - Transfer function logic for inline asm.
 405   void VisitGCCAsmStmt(const GCCAsmStmt *A, ExplodedNode *Pred,
 406                        ExplodedNodeSet &Dst);
 407
 408   /// VisitMSAsmStmt - Transfer function logic for MS inline asm.
 409   void VisitMSAsmStmt(const MSAsmStmt *A, ExplodedNode *Pred,
 410                       ExplodedNodeSet &Dst);
 411
 412   /// VisitBlockExpr - Transfer function logic for BlockExprs.
 413   void VisitBlockExpr(const BlockExpr *BE, ExplodedNode *Pred,
 414                       ExplodedNodeSet &Dst);
 415
 416   /// VisitLambdaExpr - Transfer function logic for LambdaExprs.
 417   void VisitLambdaExpr(const LambdaExpr *LE, ExplodedNode *Pred,
 418                        ExplodedNodeSet &Dst);
 419
 420   /// VisitBinaryOperator - Transfer function logic for binary operators.
 421   void VisitBinaryOperator(const BinaryOperator* B, ExplodedNode *Pred,
 422                            ExplodedNodeSet &Dst);
 423
 424
 425   /// VisitCall - Transfer function for function calls.
 426   void VisitCallExpr(const CallExpr *CE, ExplodedNode *Pred,
 427                      ExplodedNodeSet &Dst);
 428
 429   /// VisitCast - Transfer function logic for all casts (implicit and explicit).
 430   void VisitCast(const CastExpr *CastE, const Expr *Ex, ExplodedNode *Pred,
 431                  ExplodedNodeSet &Dst);
 432
 433   /// VisitCompoundLiteralExpr - Transfer function logic for compound literals.
 434   void VisitCompoundLiteralExpr(const CompoundLiteralExpr *CL,
 435                                 ExplodedNode *Pred, ExplodedNodeSet &Dst);
 436
 437   /// Transfer function logic for DeclRefExprs and BlockDeclRefExprs.
 438   void VisitCommonDeclRefExpr(const Expr *DR, const NamedDecl *D,
 439                               ExplodedNode *Pred, ExplodedNodeSet &Dst);
 440
 441   /// VisitDeclStmt - Transfer function logic for DeclStmts.
 442   void VisitDeclStmt(const DeclStmt *DS, ExplodedNode *Pred,
 443                      ExplodedNodeSet &Dst);
 444
 445   /// VisitGuardedExpr - Transfer function logic for ?, __builtin_choose
 446   void VisitGuardedExpr(const Expr *Ex, const Expr *L, const Expr *R,
 447                         ExplodedNode *Pred, ExplodedNodeSet &Dst);
 448
 449   void VisitInitListExpr(const InitListExpr *E, ExplodedNode *Pred,
 450                          ExplodedNodeSet &Dst);
 451
 452   /// VisitLogicalExpr - Transfer function logic for '&&', '||'
 453   void VisitLogicalExpr(const BinaryOperator* B, ExplodedNode *Pred,
 454                         ExplodedNodeSet &Dst);
 455
 456   /// VisitMemberExpr - Transfer function for member expressions.
 457   void VisitMemberExpr(const MemberExpr *M, ExplodedNode *Pred,
 458                        ExplodedNodeSet &Dst);
 459
 460   /// VisitAtomicExpr - Transfer function for builtin atomic expressions
 461   void VisitAtomicExpr(const AtomicExpr *E, ExplodedNode *Pred,
 462                        ExplodedNodeSet &Dst);
 463
 464   /// Transfer function logic for ObjCAtSynchronizedStmts.
 465   void VisitObjCAtSynchronizedStmt(const ObjCAtSynchronizedStmt *S,
 466                                    ExplodedNode *Pred, ExplodedNodeSet &Dst);
 467
 468   /// Transfer function logic for computing the lvalue of an Objective-C ivar.
 469   void VisitLvalObjCIvarRefExpr(const ObjCIvarRefExpr *DR, ExplodedNode *Pred,
 470                                 ExplodedNodeSet &Dst);
 471
 472   /// VisitObjCForCollectionStmt - Transfer function logic for
 473   ///  ObjCForCollectionStmt.
 474   void VisitObjCForCollectionStmt(const ObjCForCollectionStmt *S,
 475                                   ExplodedNode *Pred, ExplodedNodeSet &Dst);
 476
 477   void VisitObjCMessage(const ObjCMessageExpr *ME, ExplodedNode *Pred,
 478                         ExplodedNodeSet &Dst);
 479
 480   /// VisitReturnStmt - Transfer function logic for return statements.
 481   void VisitReturnStmt(const ReturnStmt *R, ExplodedNode *Pred,
 482                        ExplodedNodeSet &Dst);
 483
 484   /// VisitOffsetOfExpr - Transfer function for offsetof.
 485   void VisitOffsetOfExpr(const OffsetOfExpr *Ex, ExplodedNode *Pred,
 486                          ExplodedNodeSet &Dst);
 487
 488   /// VisitUnaryExprOrTypeTraitExpr - Transfer function for sizeof.
 489   void VisitUnaryExprOrTypeTraitExpr(const UnaryExprOrTypeTraitExpr *Ex,
 490                                      ExplodedNode *Pred, ExplodedNodeSet &Dst);
 491
 492   /// VisitUnaryOperator - Transfer function logic for unary operators.
 493   void VisitUnaryOperator(const UnaryOperator* B, ExplodedNode *Pred,
 494                           ExplodedNodeSet &Dst);
 495
 496   /// Handle ++ and -- (both pre- and post-increment).
 497   void VisitIncrementDecrementOperator(const UnaryOperator* U,
 498                                        ExplodedNode *Pred,
 499                                        ExplodedNodeSet &Dst);
 500
 501   void VisitCXXBindTemporaryExpr(const CXXBindTemporaryExpr *BTE,
 502                                  ExplodedNodeSet &PreVisit,
 503                                  ExplodedNodeSet &Dst);
 504
 505   void VisitCXXCatchStmt(const CXXCatchStmt *CS, ExplodedNode *Pred,
 506                          ExplodedNodeSet &Dst);
 507
 508   void VisitCXXThisExpr(const CXXThisExpr *TE, ExplodedNode *Pred,
 509                         ExplodedNodeSet & Dst);
 510
 511   void VisitCXXConstructExpr(const CXXConstructExpr *E, ExplodedNode *Pred,
 512                              ExplodedNodeSet &Dst);
 513
 514   void VisitCXXDestructor(QualType ObjectType, const MemRegion *Dest,
 515                           const Stmt *S, bool IsBaseDtor,
 516                           ExplodedNode *Pred, ExplodedNodeSet &Dst,
 517                           const EvalCallOptions &Options);
 518
 519   void VisitCXXNewAllocatorCall(const CXXNewExpr *CNE,
 520                                 ExplodedNode *Pred,
 521                                 ExplodedNodeSet &Dst);
 522
 523   void VisitCXXNewExpr(const CXXNewExpr *CNE, ExplodedNode *Pred,
 524                        ExplodedNodeSet &Dst);
 525
 526   void VisitCXXDeleteExpr(const CXXDeleteExpr *CDE, ExplodedNode *Pred,
 527                           ExplodedNodeSet &Dst);
 528
 529   /// Create a C++ temporary object for an rvalue.
 530   void CreateCXXTemporaryObject(const MaterializeTemporaryExpr *ME,
 531                                 ExplodedNode *Pred,
 532                                 ExplodedNodeSet &Dst);
 533
 534   /// evalEagerlyAssumeBinOpBifurcation - Given the nodes in 'Src', eagerly assume symbolic
 535   ///  expressions of the form 'x != 0' and generate new nodes (stored in Dst)
 536   ///  with those assumptions.
 537   void evalEagerlyAssumeBinOpBifurcation(ExplodedNodeSet &Dst, ExplodedNodeSet &Src,
 538                          const Expr *Ex);
 539
 540   static std::pair<const ProgramPointTag *, const ProgramPointTag *>
 541     geteagerlyAssumeBinOpBifurcationTags();
 542
 543   SVal evalMinus(SVal X) {
 544     return X.isValid() ? svalBuilder.evalMinus(X.castAs<NonLoc>()) : X;
 545   }
 546
 547   SVal evalComplement(SVal X) {
 548     return X.isValid() ? svalBuilder.evalComplement(X.castAs<NonLoc>()) : X;
 549   }
 550
 551   ProgramStateRef handleLValueBitCast(ProgramStateRef state, const Expr *Ex,
 552                                       const LocationContext *LCtx, QualType T,
 553                                       QualType ExTy, const CastExpr *CastE,
 554                                       StmtNodeBuilder &Bldr,
 555                                       ExplodedNode *Pred);
 556
 557   ProgramStateRef handleLVectorSplat(ProgramStateRef state,
 558                                      const LocationContext *LCtx,
 559                                      const CastExpr *CastE,
 560                                      StmtNodeBuilder &Bldr,
 561                                      ExplodedNode *Pred);
 562
 563   void handleUOExtension(ExplodedNodeSet::iterator I,
 564                          const UnaryOperator* U,
 565                          StmtNodeBuilder &Bldr);
 566
 567 public:
 568   SVal evalBinOp(ProgramStateRef state, BinaryOperator::Opcode op,
 569                  NonLoc L, NonLoc R, QualType T) {
 570     return svalBuilder.evalBinOpNN(state, op, L, R, T);
 571   }
 572
 573   SVal evalBinOp(ProgramStateRef state, BinaryOperator::Opcode op,
 574                  NonLoc L, SVal R, QualType T) {
 575     return R.isValid() ? svalBuilder.evalBinOpNN(state, op, L,
 576                                                  R.castAs<NonLoc>(), T) : R;
 577   }
 578
 579   SVal evalBinOp(ProgramStateRef ST, BinaryOperator::Opcode Op,
 580                  SVal LHS, SVal RHS, QualType T) {
 581     return svalBuilder.evalBinOp(ST, Op, LHS, RHS, T);
 582   }
 583
 584 protected:
 585   /// evalBind - Handle the semantics of binding a value to a specific location.
 586   ///  This method is used by evalStore, VisitDeclStmt, and others.
 587   void evalBind(ExplodedNodeSet &Dst, const Stmt *StoreE, ExplodedNode *Pred,
 588                 SVal location, SVal Val, bool atDeclInit = false,
 589                 const ProgramPoint *PP = nullptr);
 590
 591   /// Call PointerEscape callback when a value escapes as a result of bind.
 592   ProgramStateRef processPointerEscapedOnBind(ProgramStateRef State,
 593                                               SVal Loc,
 594                                               SVal Val,
 595                                               const LocationContext *LCtx) override;
 596   /// Call PointerEscape callback when a value escapes as a result of
 597   /// region invalidation.
 598   /// \param[in] ITraits Specifies invalidation traits for regions/symbols.
 599   ProgramStateRef notifyCheckersOfPointerEscape(
 600                            ProgramStateRef State,
 601                            const InvalidatedSymbols *Invalidated,
 602                            ArrayRef<const MemRegion *> ExplicitRegions,
 603                            ArrayRef<const MemRegion *> Regions,
 604                            const CallEvent *Call,
 605                            RegionAndSymbolInvalidationTraits &ITraits) override;
 606
 607   /// A simple wrapper when you only need to notify checkers of pointer-escape
 608   /// of a single value.
 609   ProgramStateRef escapeValue(ProgramStateRef State, SVal V,
 610                               PointerEscapeKind K) const;
 611
 612 public:
 613   // FIXME: 'tag' should be removed, and a LocationContext should be used
 614   // instead.
 615   // FIXME: Comment on the meaning of the arguments, when 'St' may not
 616   // be the same as Pred->state, and when 'location' may not be the
 617   // same as state->getLValue(Ex).
 618   /// Simulate a read of the result of Ex.
 619   void evalLoad(ExplodedNodeSet &Dst,
 620                 const Expr *NodeEx,  /* Eventually will be a CFGStmt */
 621                 const Expr *BoundExpr,
 622                 ExplodedNode *Pred,
 623                 ProgramStateRef St,
 624                 SVal location,
 625                 const ProgramPointTag *tag = nullptr,
 626                 QualType LoadTy = QualType());
 627
 628   // FIXME: 'tag' should be removed, and a LocationContext should be used
 629   // instead.
 630   void evalStore(ExplodedNodeSet &Dst, const Expr *AssignE, const Expr *StoreE,
 631                  ExplodedNode *Pred, ProgramStateRef St, SVal TargetLV, SVal Val,
 632                  const ProgramPointTag *tag = nullptr);
 633
 634   /// Return the CFG element corresponding to the worklist element
 635   /// that is currently being processed by ExprEngine.
 636   CFGElement getCurrentCFGElement() {
 637     return (*currBldrCtx->getBlock())[currStmtIdx];
 638   }
 639
 640   /// Create a new state in which the call return value is binded to the
 641   /// call origin expression.
 642   ProgramStateRef bindReturnValue(const CallEvent &Call,
 643                                   const LocationContext *LCtx,
 644                                   ProgramStateRef State);
 645
 646   /// Evaluate a call, running pre- and post-call checks and allowing checkers
 647   /// to be responsible for handling the evaluation of the call itself.
 648   void evalCall(ExplodedNodeSet &Dst, ExplodedNode *Pred,
 649                 const CallEvent &Call);
 650
 651   /// Default implementation of call evaluation.
 652   void defaultEvalCall(NodeBuilder &B, ExplodedNode *Pred,
 653                        const CallEvent &Call,
 654                        const EvalCallOptions &CallOpts = {});
 655
 656 private:
 657   void evalLoadCommon(ExplodedNodeSet &Dst,
 658                       const Expr *NodeEx,  /* Eventually will be a CFGStmt */
 659                       const Expr *BoundEx,
 660                       ExplodedNode *Pred,
 661                       ProgramStateRef St,
 662                       SVal location,
 663                       const ProgramPointTag *tag,
 664                       QualType LoadTy);
 665
 666   // FIXME: 'tag' should be removed, and a LocationContext should be used
 667   // instead.
 668   void evalLocation(ExplodedNodeSet &Dst,
 669                     const Stmt *NodeEx, /* This will eventually be a CFGStmt */
 670                     const Stmt *BoundEx,
 671                     ExplodedNode *Pred,
 672                     ProgramStateRef St, SVal location,
 673                     const ProgramPointTag *tag, bool isLoad);
 674
 675   /// Count the stack depth and determine if the call is recursive.
 676   void examineStackFrames(const Decl *D, const LocationContext *LCtx,
 677                           bool &IsRecursive, unsigned &StackDepth);
 678
 679   enum CallInlinePolicy {
 680     CIP_Allowed,
 681     CIP_DisallowedOnce,
 682     CIP_DisallowedAlways
 683   };
 684
 685   /// See if a particular call should be inlined, by only looking
 686   /// at the call event and the current state of analysis.
 687   CallInlinePolicy mayInlineCallKind(const CallEvent &Call,
 688                                      const ExplodedNode *Pred,
 689                                      AnalyzerOptions &Opts,
 690                                      const EvalCallOptions &CallOpts);
 691
 692   /// Checks our policies and decides weither the given call should be inlined.
 693   bool shouldInlineCall(const CallEvent &Call, const Decl *D,
 694                         const ExplodedNode *Pred,
 695                         const EvalCallOptions &CallOpts = {});
 696
 697   bool inlineCall(const CallEvent &Call, const Decl *D, NodeBuilder &Bldr,
 698                   ExplodedNode *Pred, ProgramStateRef State);
 699
 700   /// Conservatively evaluate call by invalidating regions and binding
 701   /// a conjured return value.
 702   void conservativeEvalCall(const CallEvent &Call, NodeBuilder &Bldr,
 703                             ExplodedNode *Pred, ProgramStateRef State);
 704
 705   /// Either inline or process the call conservatively (or both), based
 706   /// on DynamicDispatchBifurcation data.
 707   void BifurcateCall(const MemRegion *BifurReg,
 708                      const CallEvent &Call, const Decl *D, NodeBuilder &Bldr,
 709                      ExplodedNode *Pred);
 710
 711   bool replayWithoutInlining(ExplodedNode *P, const LocationContext *CalleeLC);
 712
 713   /// Models a trivial copy or move constructor or trivial assignment operator
 714   /// call with a simple bind.
 715   void performTrivialCopy(NodeBuilder &Bldr, ExplodedNode *Pred,
 716                           const CallEvent &Call);
 717
 718   /// If the value of the given expression \p InitWithAdjustments is a NonLoc,
 719   /// copy it into a new temporary object region, and replace the value of the
 720   /// expression with that.
 721   ///
 722   /// If \p Result is provided, the new region will be bound to this expression
 723   /// instead of \p InitWithAdjustments.
 724   ProgramStateRef createTemporaryRegionIfNeeded(ProgramStateRef State,
 725                                                 const LocationContext *LC,
 726                                                 const Expr *InitWithAdjustments,
 727                                                 const Expr *Result = nullptr);
 728
 729   /// Returns a region representing the first element of a (possibly
 730   /// multi-dimensional) array, for the purposes of element construction or
 731   /// destruction.
 732   ///
 733   /// On return, \p Ty will be set to the base type of the array.
 734   ///
 735   /// If the type is not an array type at all, the original value is returned.
 736   /// Otherwise the "IsArray" flag is set.
 737   static SVal makeZeroElementRegion(ProgramStateRef State, SVal LValue,
 738                                     QualType &Ty, bool &IsArray);
 739
 740   /// For a DeclStmt or CXXInitCtorInitializer, walk backward in the current CFG
 741   /// block to find the constructor expression that directly constructed into
 742   /// the storage for this statement. Returns null if the constructor for this
 743   /// statement created a temporary object region rather than directly
 744   /// constructing into an existing region.
 745   const CXXConstructExpr *findDirectConstructorForCurrentCFGElement();
 746
 747   /// Update the program state with all the path-sensitive information
 748   /// that's necessary to perform construction of an object with a given
 749   /// syntactic construction context. If the construction context is unavailable
 750   /// or unusable for any reason, a dummy temporary region is returned, and the
 751   /// IsConstructorWithImproperlyModeledTargetRegion flag is set in \p CallOpts.
 752   /// Returns the updated program state and the new object's this-region.
 753   std::pair<ProgramStateRef, SVal> prepareForObjectConstruction(
 754       const Expr *E, ProgramStateRef State, const LocationContext *LCtx,
 755       const ConstructionContext *CC, EvalCallOptions &CallOpts);
 756
 757   /// Store the location of a C++ object corresponding to a statement
 758   /// until the statement is actually encountered. For example, if a DeclStmt
 759   /// has CXXConstructExpr as its initializer, the object would be considered
 760   /// to be "under construction" between CXXConstructExpr and DeclStmt.
 761   /// This allows, among other things, to keep bindings to variable's fields
 762   /// made within the constructor alive until its declaration actually
 763   /// goes into scope.
 764   static ProgramStateRef addObjectUnderConstruction(
 765       ProgramStateRef State,
 766       llvm::PointerUnion<const Stmt *, const CXXCtorInitializer *> P,
 767       const LocationContext *LC, SVal V);
 768
 769   /// Mark the object sa fully constructed, cleaning up the state trait
 770   /// that tracks objects under construction.
 771   static ProgramStateRef finishObjectConstruction(
 772       ProgramStateRef State,
 773       llvm::PointerUnion<const Stmt *, const CXXCtorInitializer *> P,
 774       const LocationContext *LC);
 775
 776   /// If the given statement corresponds to an object under construction,
 777   /// being part of its construciton context, retrieve that object's location.
 778   static Optional<SVal> getObjectUnderConstruction(
 779       ProgramStateRef State,
 780       llvm::PointerUnion<const Stmt *, const CXXCtorInitializer *> P,
 781       const LocationContext *LC);
 782
 783   /// If the given expression corresponds to a temporary that was used for
 784   /// passing into an elidable copy/move constructor and that constructor
 785   /// was actually elided, track that we also need to elide the destructor.
 786   static ProgramStateRef elideDestructor(ProgramStateRef State,
 787                                          const CXXBindTemporaryExpr *BTE,
 788                                          const LocationContext *LC);
 789
 790   /// Stop tracking the destructor that corresponds to an elided constructor.
 791   static ProgramStateRef
 792   cleanupElidedDestructor(ProgramStateRef State,
 793                           const CXXBindTemporaryExpr *BTE,
 794                           const LocationContext *LC);
 795
 796   /// Returns true if the given expression corresponds to a temporary that
 797   /// was constructed for passing into an elidable copy/move constructor
 798   /// and that constructor was actually elided.
 799   static bool isDestructorElided(ProgramStateRef State,
 800                                  const CXXBindTemporaryExpr *BTE,
 801                                  const LocationContext *LC);
 802
 803   /// Check if all objects under construction have been fully constructed
 804   /// for the given context range (including FromLC, not including ToLC).
 805   /// This is useful for assertions. Also checks if elided destructors
 806   /// were cleaned up.
 807   static bool areAllObjectsFullyConstructed(ProgramStateRef State,
 808                                             const LocationContext *FromLC,
 809                                             const LocationContext *ToLC);
 810 };
 811
 812 /// Traits for storing the call processing policy inside GDM.
 813 /// The GDM stores the corresponding CallExpr pointer.
 814 // FIXME: This does not use the nice trait macros because it must be accessible
 815 // from multiple translation units.
 816 struct ReplayWithoutInlining{};
 817 template <>
 818 struct ProgramStateTrait<ReplayWithoutInlining> :
 819   public ProgramStatePartialTrait<const void*> {
 820   static void *GDMIndex() { static int index = 0; return &index; }
 821 };
 822
 823 } // namespace ento
 824
 825 } // namespace clang
 826
 827 #endif // LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_EXPRENGINE_H