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